23. Merge K Soerted List

Merge Two Sorted List

解决 K sorted list, 我们先解决这个问题。

Solution 1

We can think of a head node and a pointer prev starting from the head.
When compraing l1 and l2 nodes and while both of them or not null, if l1.val is smaller, we can set prev.next to l1, and move l1 to l1.next; else we move l2. And then we move the pointer to prev.next, the node we merged just now.
And if any list reaches null, we merge all the rest of the other list since it is sorted. And we return the head.next becuase the merged list starting from head.next.

class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode prev = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;

        return head.next;
    }
}

Solution 2: Recursion

We may also think in this way. If l1.val is smaller, we will merger l1.next and l2 in the next step and return l1 as the head for next merge; vice versa. And if any of the list is null we just return the other list.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

• Time complexity for both methods are O(n + m) because they go through each of the node once in both lists.
• Space complexity for the first one is O(1) and O(n + m) for second one beacuse the recursion won't return until it reaches end of both lists.

Merge K Sorted Lists

解法一

思路

The intuitive way comes to my mind is that I can use the method of merge two sorted linked list. We can use the mergeTwoLists method, to merge k lists one by one k - 1 times.

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        } else if (len == 1) {
            return lists[0];
        }

        ListNode l1 = lists[0];
        for (int  i = 1; i < len; i++) {
            l1 = mergeTwoLists(l1, lists[i]);
        }

        return l1;
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode prev = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;

        return head.next;
    }   
}

复杂度分析

时间复杂度
Suppose there are k lists and total nodes in all lists are N. Suppose length of each list is equal, then the first merge costs O(N/k + N/k), and second O(2N/k + N/k), ... all the way to O((k - 1)N/k + N/k). Add add k - 1 merges up, it gives O(kN).
空间复杂度
O(1) because merge two linked lists is O(1).

• 然而使用 recursion 方法时会报错，不知为何。

解法二

思路

We can use a priority queue. We can first add heads of all lists into the pq. And the node with smaller value always comes before the larger one.
We initialize a head and a pointer to consttuct the merged list. Pay attention to null list node. If there is null node, we do not add it in.
While the queue is not empty, poll the first element from the pq, which is always the smallest one. And we add the next of the polled element to the pq, unless it is null.
Finally, we return the head.next, which is the start of the merged list.

代码

class ListNode() {
    int val;
    ListNode next;
    public ListNode(int x) {
        val = x;
    }
}
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (list.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        PriorityQueue<ListNode> pq = new PriorityQueue<>((l1, l2)-> l1.val - l2.val);
        for (ListNode i : lists) {
            if (i != null) { // IMPORTANT!
                pq.offer(i);
            }
        }

        ListNode head = new ListNode(-1);
        ListNode prev = head;
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            prev.next = node;
            prev = prev.next;
            if (node.next != null) {
                pq.offer(node.next);
            }
        }

        return head.next;
    }
}

复杂度分析

时间复杂度
O(Nlog(k)) beacuse we process each node exactly once. And the poll() and offer() opertion for each node costs O(log(k)) time.
空间复杂度
We keep the size of the pq O(k). Because there are k nodes initially, and every time we poll a node, we add its next node into the queue.

Takeaway

• 使用 PriorityQueue 时，一定要确定所用泛型是否可比较。如果不能比较，需要重写 Comparator。
• 每次添加节点进 pq, 需要判断其是否为空。空节点没有意义。

本作品采用《CC 协议》，转载必须注明作者和本文链接