23 合并K个升序链表

leetcode 23 合并K个升序链表

分治归并思路

思路类似于数组的归并排序，两两组合，每次由两个链表合并

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }
    public ListNode merge(ListNode[] lists,int L,int R){
        if(L>R){
            return null;
        }
        if(L==R){
            return lists[L];
        }
        // int mid = R-(R-L)/2;
        int mid = (L + R) >> 1;
        return mergeTwoList(merge(lists,L,mid),merge(lists,mid+1,R));
    }
    public ListNode mergeTwoList(ListNode list1,ListNode list2){
        if(list1==null | list2==null){
            return list1==null?list2 : list1;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        ListNode aPtr = list1;
        ListNode bPtr = list2;
        while(aPtr != null && bPtr != null){
            if(aPtr.val < bPtr.val){
                tail.next = aPtr;
                aPtr = aPtr.next;
            }else{
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = aPtr != null? aPtr : bPtr;
        return head.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

优先队列思路

优先队列中存n个队列的头部，让优先队列来进行排序，降低复杂度（注意：需要重写优先队列的Compare逻辑）

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    class Comp implements Comparable<Comp> {
        Comp(ListNode node,int val){
            this.node = node;
            this.val = val;
        }
        ListNode node;
        int val;
        public int compareTo(Comp comp2){
            return this.val - comp2.val;
        }
    }
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<Comp> queue = new PriorityQueue<Comp>();
        for(int i = 0;i<lists.length;i++){
            if(lists[i] != null){
                queue.offer(new Comp(lists[i],lists[i].val));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while(!queue.isEmpty()){
            Comp c = queue.poll();
            tail.next = c.node;
            tail = tail.next;
            if(c.node.next != null){
                queue.offer(new Comp(c.node.next,c.node.next.val));
            }
        }
        return head.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42