Merge Sort Template

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

private int[] temp = new int[5_0000];
private void mergeSort(int[] nums, int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = l + r >> 1;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (nums[i] < nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    while (j <= r) {
        temp[k++] = nums[j++];
    }
    for (i = l, j = 0; i <= r; i++, j++) {
        nums[i] = temp[j];
    }
}

Questions

23. Merge k Sorted Lists

Description

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• 10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length won't exceed 10^4.

---

解题

方法一

思路

视频详解: https://www.youtube.com/watch?v=ptYUCjfNhJY

用PriorityQueue做最小堆，每次最小的值出来

代码

public ListNode mergeKLists(ListNode[] lists) {

    // 初始化
    ListNode head = new ListNode(-1);
    ListNode tail = head;

    // 构建最小堆
    PriorityQueue<ListNode> miniHeap = new PriorityQueue<>((n1, n2) -> {
        return n1.val - n2.val;
    });

    // 把所有list的第一个node，放到最小堆
    for (ListNode node : lists) {
        if (node != null) miniHeap.offer(node);
    }

    while (!miniHeap.isEmpty()) {
        // 最小的值出来
        tail.next = miniHeap.poll();
        // 指针往后挪一个
        tail = tail.next;
        // 如果这个最小的值后面还有节点，那就放进去
        if (tail.next != null) {
            miniHeap.offer(tail.next);
        }
    }
    return head.next;
}

复杂度分析

• 时间复杂度: O( n * log(k) )
• 空间复杂度: O(k)

---

方法二

思路

merge sort

代码

/**
 * 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 {
    // 15 min

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

    private ListNode mergeKLists(ListNode[] lists, int l, int r) {
        if (l < r) {
            int mid = l + r >> 1;
            ListNode node1 = mergeKLists(lists, l, mid);
            ListNode node2 = mergeKLists(lists, mid + 1, r);
            return merge2Lists(node1, node2);
        } else if (l == r) {
            return lists[l];
        } else {
            return null;
        }
    }

    private ListNode merge2Lists(ListNode node1, ListNode node2) {
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;
        while (node1 != null && node2 != null) {
            if (node1.val < node2.val) {
                head.next = node1;
                node1 = node1.next;
            } else {
                head.next = node2;
                node2 = node2.next;
            }
            head = head.next;
        }
        if (node1 != null) {
            head.next = node1;
        }
        if (node2 != null) {
            head.next = node2;
        }
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度: O(nlogn)
• 空间复杂度: O(1)

---