LC023-合并K個升序連結清單

23.合并K個升序連結清單

目錄

• ​​23.合并K個升序連結清單​​

• ​​利用堆做排序​​
• ​​兩兩合并​​
• ​​分治​​

給你一個連結清單數組，每個連結清單都已經按升序排列。

請你将所有連結清單合并到一個升序連結清單中，傳回合并後的連結清單。

示例 1：

輸入：lists = [[1,4,5],[1,3,4],[2,6]]
輸出：[1,1,2,3,4,4,5,6]
解釋：連結清單數組如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它們合并到一個有序連結清單中得到。
1->1->2->3->4->4->5->6      

利用堆做排序

需要一種輔助資料結構-​

​堆​

​，有了堆這個資料結構，難度等級是困難的題目，瞬間變成簡單了。

隻把k個連結清單的第一個節點放入到堆中

之後不斷從堆中取出節點，如果這個節點還有下一個節點，

就将下個節點也放入堆中

public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        //建立一個最小的堆,并定義好内部排序
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return (o1.val - o2.val);
            }
        });

        ListNode dummy=new ListNode(-1);
        ListNode cur=dummy;
        //把每個連結清單的第一個節點放入到堆中
        for (int i = 0; i <lists.length ; i++) {
            ListNode head=lists[i];
            if (head!=null){
                queue.add(head);
            }
        }

        //  poll()把檢索并删除此隊列的頭，如果此隊列為空，則傳回 null 。
        //之後不斷從堆中取出節點，如果這個節點還有下一個節點，
        //就将下個節點也放入堆中
        while (queue.size()>0){
            ListNode node=queue.poll();
            cur.next=node;
            cur=cur.next;
            if (node.next!=null){
                queue.add(node.next);
            }
        }
        cur.next=null;
        return  dummy.next;



    }      

兩兩合并

public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        ListNode newList = lists[0];
        for (int i = 1; i < lists.length; i++) {
            newList = merge(newList, lists[i]);
        }
        return newList;
    }

//兩兩合并的代碼，直接把下面這段代碼拿來用即可
    public ListNode merge(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return (a == null) ? b : a;
        }
        if (a.val <= b.val) {
            a.next = merge(a.next, b);
            return a;
        } else {
            b.next = merge(a, b.next);
            return b;
        }
    }
}      

分治

分治就是不斷縮小其規模，再不斷合并擴大的過程

• 分治就是不斷縮小其規模,在不斷擴大的過程
• 一開始的數組的規模是6,我們找到中間點,将一分為二,然後再分,直到不能在分(規模為一),便傳回
• 之後合并,合并接用合并兩個排序連結清單的代碼
• 當兩個規模最小的連結清單合并完後,其規模就變大,
• 然後不斷重複這個合并過程,直到最終得到一個有序的連結清單

package com.nie.LEE;

public class LEE023L {
    /*
    分治就是不斷縮小其規模,在不斷擴大的過程
    一開始的數組的規模是6,我們找到中間點,将一分為二,然後再分,直到不能在分(規模為一),
    便傳回
    之後合并,合并接用合并兩個排序連結清單的代碼
    當兩個規模最小的連結清單合并完後,其規模就變大,
    然後不斷重複這個合并過程,直到最終得到一個有序的連結清單
      */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return  helper(lists,0,lists.length-1);
    }
    //通過mid将數組一分為二，并不斷縮小規模，當規模為1時傳回并開始合并
    //通過合并兩個連結清單，不斷增大其規模，整體看就是不斷縮小-最後不斷擴大的過程
    private ListNode helper(ListNode[] lists, int begin, int end) {
        if (begin==end){
            return  lists[begin];
        }
        int mid=begin+(end-begin)/2;
        ListNode left=helper(lists,begin,mid);
        ListNode right=helper(lists,mid+1,end);
        return  merge(left,right);
    }

合并兩個有序連結清單
    public ListNode merge(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return (a == null) ? b : a;
        }
        if (a.val <= b.val) {
            a.next = merge(a.next, b);
            return a;
        } else {
            b.next = merge(a, b.next);
            return b;
        }
    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}