LeetCode 题解-15. 3Sum - 张磊的技术笔记

对Leetcode 23. Merge k Sorted Lists 题目的求解。

Problem Description#

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example 1#

1
Input:
2
[
3
  1->4->5,
4
  1->3->4,
5
  2->6
6
]
7
Output: 1->1->2->3->4->4->5->6

Analysis#

之前做过将两个linked list 合并的题目，即为归并排序的思路，这道题要求我们将k个排好序的链表做归并．有两种思路

将k个list的归并不断分解为两个list的归并，即采用二分的方法
采用最直观的思路，既然k个列表都是排好序的，那么在任何时刻，表头的元素都是当前最小的元素．可以使用priority queue来找到最小的元素，并且更换表头．

Solution 1#

1
class Solution {
2
    public static ListNode mergeKLists(ListNode[] lists) {
3
        if (lists.length == 0) return null;
4
        return part(lists, 0, lists.length - 1);
5
    }
6
    public static ListNode part(ListNode[] lists,int s, int t) {
7
        if (s == t) return lists[s];
8
        ListNode l1 = part(lists, s, (s+t)/2);
9
        ListNode l2 = part(lists, (s+t)/2+1, t);
10
        return merge(l1, l2);
11
    }
12
    public static ListNode merge(ListNode l1, ListNode l2){
13
        ListNode zero = new ListNode(0);
14
        ListNode tmp = zero;
15
        while (l1 != null && l2 != null){
16
            if (l1.val < l2.val){ tmp.next = l1; l1 = l1.next;}
17
            else {tmp.next = l2; l2 = l2.next;}
18
            tmp = tmp.next;
19
        }
20
        while (l1 != null) {tmp.next = l1; l1 = l1.next; tmp = tmp.next;}
21
        while (l2 != null) {tmp.next = l2; l2 = l2.next; tmp = tmp.next;}
22
        return zero.next;
23
    }
24
}

Solution 2#

1
class Solution{
2
        public static ListNode mergeKLists(ListNode[] lists) {
3
        if (lists.length == 0) return null;
4
        //priority queue
5
        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.length,
6
            new Comparator<ListNode>() {
7
                @Override
8
                public int compare(ListNode l1, ListNode l2){
9
                    if (l1.val < l2.val){
10
                        return -1;
11
                    }
12
                    else if (l1.val > l2.val){
13
                        return 1;
14
                    }
15
                    else return 0;
16
                }
17
            }
18
        );
19
        for (ListNode l : lists){
20
            if (l != null) q.add(l);
21
        }
22
        ListNode zero = new ListNode(0);
23
        ListNode tmp = zero;
24
        while (!q.isEmpty()){
25
            ListNode l = q.poll();
26
            tmp.next = l;
27
            tmp = tmp.next;
28
            if (l.next != null) q.add(l.next);
29
        }
30
        return zero.next;
31

32
    }
33
}

Solution 3#

1
class Solution {
2
    public static ListNode mergeKLists(ListNode[] lists) {
3
        if (lists.length ==0) return null;
4
        ListNode zero = new ListNode(0);
5
        ListNode tmp = zero;
6
        while (true){
7
            ListNode min_node = find_min_node(lists);
8
            if (min_node == null) break;
9
            tmp.next = min_node;
10
            tmp = tmp.next;
11
        }
12
        return zero.next;
13
    }
14
    public static ListNode find_min_node(ListNode[] lists) {
15
        ListNode res = help(lists, 0, lists.length-1);
16
        if (res == null) return null;
17
        for (int i = 0; i < lists.length; ++i){
18
            //System.out.print(res);
19
            //System.out.println(lists[i]);
20
            if (res.equals(lists[i])){
21
                lists[i] = res.next;
22
                break;
23
            }
24
        }
25
        return res;
26
    }
27
    public static ListNode help(ListNode[] lists, int s, int t){
28
        //System.out.printf("%d %d\n", s, t);
29
        if (s == t) return lists[s];
30
        ListNode l1 = help(lists, s, (t+s)/2);
31
        ListNode l2 = help(lists, (t+s)/2 + 1, t);
32
        if (l1 == null && l2 == null ) return null;
33
        if (l1 == null) return l2;
34
        if (l2 == null) return l1;
35
        if (l1.val < l2.val) return l1;
36
        else return l2;
37
    }