[LeetCode] 23. Merge k Sorted Lists

Posted on | In

Problem

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

Example:

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

Explanation 1

  1. We can use divide and conquer method to solve this problem. For example, if we have 6 ListNode, then we can solve ListNode1 with ListNode4, ListNode2 with ListNode5, ListNode3 with ListNode6.

  2. Then, we have 3 ListNode need to sort. We then sort ListNode1 with ListNode3.

  3. Then, we have 2 ListNode need to sort. We then sort ListNode1 with ListNode2.

  4. Finally, we return the result of ListNode1.

  5. Since there are $k$ ListNode in the array, similarly to merge sort, we divide $k$ ListNode takes $\log(k)$ time, and there are total of $kn$ nodes to compare, so the total time complexity is $kn\log(k)$. The space complexity is $log(k)$ because of the recursive stack.

Solution 1

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if (n < 1) return null;
        if (n == 1) return lists[0];
        while (n >= 2) {
            int mid = (n+1)/2;
            for (int i = 0; i < n/2; i++) {
                lists[i] = mergeTwoLists(lists[i], lists[i+mid]);
            }
            n = mid;
        }
        return lists[0];
    }
}

// Iterated way of merging 2 ListNode

// class Solution {
//     ListNode merge(ListNode list1, ListNode list2) {
//         ListNode dummy = new ListNode(-1);
//         ListNode pre = dummy;
//         ListNode ptr1 = list1, ptr2 = list2;
//         pre.next = ptr1;
//         while (ptr1 != null && ptr2 != null) {
//             if (ptr1.val < ptr2.val) {
//                 ptr1 = ptr1.next;
//             } else {
//                 ListNode nex = ptr2.next;
//                 pre.next = ptr2;
//                 ptr2.next = ptr1;
//                 ptr2 = nex;
//             }
//             pre = pre.next;
//         }
//         if (ptr2 != null) {
//             pre.next = ptr2;
//         }
//         return dummy.next;
//     }

//     ListNode helper(ListNode[] lists, int left, int right) {
//         while (left < right) {
//             int mid = left + (right - left) / 2;
//             return merge(helper(lists, left, mid), helper(lists, mid+1, right));
//         }
//         return lists[left];
//     }

//     public ListNode mergeKLists(ListNode[] lists) {
//         if (lists.length == 0) return null;
//         if (lists.length == 1) return lists[0];
//         return helper(lists, 0, lists.length - 1);
//     }
// }

Explanation 2

  1. We can create a min-heap by using the PriorityQueue data structure to store all ListNode. If there are $k$ ListNode inside the input array, then we store all $k$ ListNode. They are sorted by their first Node value.

  2. We create a res ListNode, then extract the minimum ListNode and put it’s value into the res ListNode. If the extracted ListNode’s next node is not empty, put it back to the priority queue. Repeat this process until the priority queue is empty.

  3. Finally return the res ListNode.

  4. Since there are $k$ ListNode in the array, and there are $n$ ListNode in each ListNode, so there are total of $kn$ elements in the array. Because each element adding to the queue costs $log(k)$ time, so the total time complexity is $kn\log(k)$. The space complexity is $O(k)$ because of the min-heap size will have maximum $k$ ListNodes.

Solution 2

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length < 1) return null;

        PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
            public int compare(ListNode l1, ListNode l2) {
                return l1.val - l2.val;
            }
        });

        for (ListNode lst : lists) {
            if (lst != null) {
                queue.offer(lst);
            }
        }

        ListNode res = new ListNode(-1);
        ListNode cur = res;
        while (!queue.isEmpty()) {
            ListNode temp = queue.poll();
            cur.next = temp;
            cur = cur.next;
            if (temp.next != null) {
                queue.offer(temp.next);
            }
        }
        return res.next;
    }
}