Merge Sort Template
Tags: java, programming, algorithms, 100daysofcode
Published: 2022-02-05 12:50:33

# Merge Sort Template

```cpp
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];
}
```

```java
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](https://www.youtube.com/watch?v=ptYUCjfNhJY)

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

### 代码

```java
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

### 代码

```java
/**
 * 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)

---