LeetCode 23. Merge k Sorted Lists

LeetCode 23. Merge k Sorted Lists

题意

合并k个链表，每个链表内部都是排好序的（从小到大），但是k个链表之间是无序的。

思路

首先，最简单的办法就是链表之间选择排序，取第一个链表的第一个节点插到结果中。然后如果链表还有节点，放回到数组中。如此往复，直到没有节点剩余。

时间复杂度O(k*n)，空间复杂度O(1)。

// from https://www.robberphex.com/merge-k-sorted-lists/
// Runtime: 420 ms Memory Usage: 38.6 MB
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;
        ListNode head = null;
        int hi = -1;
        // 选出一个head
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null && (head == null || lists[i].val < head.val)) {
                head = lists[i];
                hi = i;
            }
        }

        if (head == null)
            return head;
        lists[hi] = lists[hi].next;
        ListNode prev = head;

        while (true) {
            ListNode cur = null;
            int ci = 0;
            // 选出最小的node
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] != null && (cur == null || lists[i].val < cur.val)) {
                    cur = lists[i];
                    ci = i;
                }
            }
            if (cur == null)
                break;
            // 插入到链表中
            lists[ci] = lists[ci].next;
            prev.next = cur;
            cur.next = null;
            prev = cur;
        }

        return head;
    }
}

显然，多次对k个链表排序是很浪费的，这时候就想到了堆，只需要将k个链表构成一个堆即可。时间复杂度O(N*log(k))，空间复杂度O(1)：

构建堆有两种，一种是从底向上不断调整堆，一种是依次将元素放入堆中。显然，前一种比较省时。

// from https://www.robberphex.com/merge-k-sorted-lists/
// Runtime: 2 ms Memory Usage: 43.2 MB
class Solution {
    private int len;

    public void adjust(ListNode[] lists, int startIndex) {
        ListNode start = lists[startIndex];
        int currIndex = startIndex;
        while (currIndex < len) {
            int nextIndex = currIndex * 2 + 1;
            if (nextIndex + 1 < len && lists[nextIndex + 1].val < lists[nextIndex].val) {
                nextIndex += 1;
            }
            if (nextIndex < len && start.val > lists[nextIndex].val) {
                lists[currIndex] = lists[nextIndex];
                currIndex = nextIndex;
            } else {
                break;
            }
        }
        lists[currIndex] = start;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        len = lists.length;
        // 剔除null
        for (int i = 0; i < len; ) {
            if (lists[i] == null) {
                lists[i] = lists[--len];
            } else {
                i++;
            }
        }
        ListNode head = null;
        ListNode tail = null;
        // i==0时的调整交给下面的while循环
        for (int i = len / 2; i > 0; i--) {
            adjust(lists, i);
        }
        while (len > 0) {
            adjust(lists, 0);
            if (tail == null) {
                head = tail = lists[0];
            } else {
                tail.next = lists[0];
                tail = tail.next;
            }
            if (tail.next != null) {
                lists[0] = tail.next;
            } else {
                lists[0] = lists[len - 1];
                len--;
            }
            tail.next = null;
        }
        return head;
    }
}

接下来，看了官方的解法，发现还有一种 Merge with Divide And Conquer，如图：

和堆的解法一样，时间复杂度O(N*log(k))，空间复杂度O(1)：

// from https://www.robberphex.com/merge-k-sorted-lists/
// Runtime: 2 ms Memory Usage: 41.6 MB
class Solution {
    private ListNode mergeTwoLists(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        int med = (left + right) / 2;
        ListNode l1 = mergeTwoLists(lists, left, med);
        ListNode l2 = mergeTwoLists(lists, med + 1, right);

        ListNode head = null;
        ListNode tail = null;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                if (tail == null) {
                    head = tail = l1;
                } else {
                    tail.next = l1;
                    tail = tail.next;
                }
                l1 = l1.next;
            } else {
                if (tail == null) {
                    head = tail = l2;
                } else {
                    tail.next = l2;
                    tail = tail.next;
                }
                l2 = l2.next;
            }
            tail.next = null;
        }
        if (tail != null) {
            tail.next = l1 != null ? l1 : l2;
        } else {
            head = l1 != null ? l1 : l2;
        }
        return head;
    }

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

在做LeetCode 215. Kth Largest Element in an Array的时候，发现自己几乎忘记了堆排序，很惭愧。所以做这道题目复习下。