合并链表

> 下面的问题解析中的**为头结点 `head` 赋初始值是针对的牛客网上相应的题目**（[NC33 合并两个排序的链表](https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=117&tqId=37735&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26pageSize%3D50%26search%3D%25E9%2593%25BE%25E8%25A1%25A8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&difficulty=undefined&judgeStatus=undefined&tags=&title=%E9%93%BE%E8%A1%A8)），因为牛客网上的题目中 `ListNode`**没有空参构造函数**，所以**其实例中 `val` 不能为空**，而 Leetcode 上对应的题目（[21. 合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists)）中 `ListNode` 有空参构造函数，所以其实例中 `val` 可以为空。

## 1. 合并两个排序的链表

> 题目来源：[21. 合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists)

### 1.1 题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

**示例 1：**

![](https://notebook.ricear.com/media/202206/2022-06-25_110320_875719.png)

```txt
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
```

**示例 2：**

```txt
输入：l1 = [], l2 = []
输出：[]
```

**示例 3：**

```txt
输入：l1 = [], l2 = [0]
输出：[0]
```

**提示：**

- 两个链表的节点数目范围是 [0, 50]
- -100 <= Node.val <= 100
- l1 和 l2 均按 非递减顺序 排列

### 1.2 问题解析

1. 解答此题时可以定义一个**头结点** `head`，头结点对应的 `val`**可以自定义**，因为后面返回最后结果时是从头结点的下一个节点开始，即 `head.next`，因此头结点的值对最终结果没有影响，同时定义一个**临时指针** `p`，用来**连接后面的节点**，其中 `p` 开始的时候**指向** `head`，即 `p = head`。
   ![](https://notebook.ricear.com/media/202206/2022-06-25_114548_778589.png)
2. 然后比较两个链表各自当前节点的值 `list1.val` 和 `list2.val`：
   1. 如果 `list1.val`**小于等于** `list2.val`，则**将 `p` 指向节点的指针指向** `list1`，同时**将 `p` 指向** `list1`，然后**将 `list1` 指向下一个节点**，即 `p.next = list1; p = list1; list1 = list1.next; `
      ![](https://notebook.ricear.com/media/202206/2022-06-25_114807_951268.gif)
   2. 如果 `list1.val`**大于** `list2.val`，则**将 `p` 指向节点的指针指向** `list2`，同时**将 `p` 指向** `list2`，然后**将 `list2` 指向下一个节点**，即 `p.next = list2; p = list2; list2 = list2.next; `
      ![](https://notebook.ricear.com/media/202206/2022-06-25_115009_838082.gif)
3. 最后将 `list1` 和 `list2` 中**不为空的部分链接到前面已经合并后的链表**：
   ![](https://notebook.ricear.com/media/202206/2022-06-25_115347_100070.gif)

### 1.3 参考代码

```java
/**
 * 合并两个有序链表
 * @param node1 第一个链表
 * @param node2 第二个链表
 * @return  合并后的链表
 */
public ListNode merge(ListNode list1,ListNode list2) {
    ListNode head = new ListNode(Integer.MIN_VALUE), p = head;
  
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            p.next = list1;
            p = list1;
            list1 = list1.next;
        } else {
            p.next = list2;
            p = list2;
            list2 = list2.next;
        }
    }
  
    if (list1 != null) {p.next = list1;}
    else if (list2 != null) {p.next = list2;}
  
    return head.next;
}
```

### 1.4 扩展题目

#### 1.4.1 合并两个排序的数组

> 题目来源：[88. 合并两个有序数组](https://leetcode.cn/problems/merge-sorted-array)。

##### 1.4.1.1 题目

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

**示例 1：**

```txt
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
```

**示例 2：**

```txt
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
```

**示例 3：**

```txt
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
```

**提示：**

* nums1.length == m + n
* nums2.length == n
* 0 <= m, n <= 200
* 1 <= m + n <= 200
* -109 <= nums1[i], nums2[j] <= 109

**进阶：** 你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

##### 1.4.1.2 问题解析

1. 初始时 $i=m-1$，$j=n-1$，$k=m+n-1$。
2. 如果 $i>=0$ 并且 $j>=0$：

1. 如果 $nums2[j]>=nums1[i]$：将 $nums2[j]$ 放到 $nums1[k]$ 的位置上，同时将 $j$ 的值减 1。
   2. 如果 $nums1[i]>nums2[j]$：将 $nums1[i]$ 放到 $nums1[k]$ 的位置上，同时将 $i$ 的值减 1。
   3. 最后统一将 $k$ 的值减 1。
3. 如果最后 $i<0$，说明 $nums1$ 已经遍历完了，$nums2$ 还没有遍历完，此时 $nums1$ 的元素都已经移动到了对应的位置上，而且此时 $nums2$ 中剩余的元素都比 $nums1$ 中已经存在的元素小，因此将 $nums2$ 中还未遍历完的元素从 $nums1$ 的起始位置依次存放即可。

![](/media/202106/88-合并两个有序数组（解法二：从后向前）_1624193151.gif)

##### 1.4.1.3 参考代码

```java
/**
 * 88. 合并两个有序数组
 *
 * @param nums1
 * @param m
 * @param nums2
 * @param n
 */
public void mergeV2(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    //  从后向前依次遍历 nums1 和 nums2
    while (i >= 0 && j >= 0) {
        if (nums2[j] >= nums1[i]) {
            // 如果 nums2[j] >= nums1[i]，则将 nums2[j] 放到 nums1[k] 的位置上，同时将 j 的值减 1
            nums1[k] = nums2[j];
            j--;
        } else if (nums1[i] > nums2[j]) {
            // 如果 nums1[i] >= nums2[j]，则将 nums1[i] 放到 nums1[k] 的位置上，同时将 i 的值减 1
            nums1[k] = nums1[i];
            i--;
        }
        //  最后统一将 k 的值减 1
        k--;
    }
    //  如果最后 nums1 已经遍历完了，nums2 还没有遍历完，说明此时 nums1 中的元素都已经移动到了 nums1 的对应的位置上，而且此时 nums2 中剩余的元素都小于 nums1 中已经存在的元素，因此直接将 nums2 中还未遍历完的元素从 nums1 的起始位置依次存放即可
    if (i < 0) {
        int q = 0;
        for (int p = 0; p <= j; p++) {
            nums1[p] = nums2[q];
            q++;
        }
    }
}
```

## 2 合并 k 个排序的链表

> 题目来源：[23. 合并 K 个升序链表](https://leetcode.cn/problems/merge-k-sorted-lists)。

### 2.1 题目

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

```txt
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
```

示例 2：

```txt
输入：lists = []
输出：[]
```

示例 3：

```txt
输入：lists = [[]]
输出：[]
```

**提示：**

- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] 按 升序 排列
- lists[i].length 的总和不超过 10^4

### 2.2 问题解析

1. 如果是**两个有序链表合并**，我们可能会利用**归并排序合并阶段**的思想：
   1. **准备双指针分别放在两个链表头**，**每次取出较小的一个元素加入新的大链表**，**将其指针后移**，**继续比较**，**这样我们出去的都是最小的元素**，**自然就完成了排序**。
2. 其实这道题我们也可以**两两比较**：
   1. **只要遍历链表数组**，**取出开头的两个链表**，**按照上述思路合并**，**然后新链表再与后一个链表继续合并**，**如此循环**，**直到全部合并完成**。
      但是这样做**太浪费时间**，**效率比较低**。
3. 既然都是归并的思想了，因此我们可以按照直接归并的分治来做，而不是顺序遍历合并链表，对于这 $k$**个链表**，就相当于**合并阶段的**$k$**个子问题**，需要**划分为链表数量更少的子问题**，直到**每一组合并时是两两合并**，这个过程基于**递归**：
   1. **终止条件**：**划分的时候直到左右区间相等**或**左边大于右边**。
   2. **返回值**：**每级返回已经合并好的子问题链表**。
   3. **本级任务**：**对半划分**，**将划分后的子问题合并成新的链表**。
4. 具体做法如下：
   1. 从链表数组的**首**和**尾**开始，每次划分**从中间开始划分**，**划分成两半**，得到**左边**$\frac{n}{2}$**个链表**和**右边**$\frac{n}{2}$**个链表**。
   2. 继续不断**递归划分**，直到**每部分链表数为 1**。
   3. **将划分好的相邻两部分链表**，**按照合并两个有序链表的方式合并**，**合并好的两部分继续往上合并**，**直到最终合并成一个链表**。
      ![](https://notebook.ricear.com/media/202206/2022-06-26_122419_605515.gif)

### 2.3 参考代码

```java
/*
 * 合并 k 个有序链表
 * @param lists 链表数组
 * @return  合并后的链表
 */
public ListNode mergeKLists(ArrayList<ListNode> lists) {
    return mergeK(lists, 0, lists.size() - 1);
}

/*
 * 递归合并 k 个有序链表
 * @param lists 链表数组
 * @left    合并链表的左下标
 * @right   合并链表的右下标
 */
public ListNode mergeK(ArrayList<ListNode> lists, int left, int right) {
    if (left > right) {return null;}
    if (left == right) {return lists.get(left);}    //  中间一个的情况，直接返回这个链表
  
    int mid = (left + right) / 2;
    return merge(mergeK(lists, left, mid), mergeK(lists, mid + 1, right));  //  从中间分成两段，再将合并好的两段合并
}
```

### 2.4 扩展题目

#### 2.4.1 合并 k 个排序的数组

> 题目来源：[Merge K sorted arrays!](https://www.interviewbit.com/problems/merge-k-sorted-arrays)

##### 2.4.1.1 题目

**Problem Description**

You are given **K** sorted integer arrays in a form of 2D integer matrix **A** of size `K X N`.

You need to merge them into a single array and return it.

**Problem Constraints**
1 <= K, N <= 10^3^

0 <= A[i][j] <= 10^8^

A[i][j] <= A[i][j+1]

**Input Format**
First and only argument is an 2D integer matrix  **A** .

**Output Format**
Return a integer array denoting the merged array you get after merging all the arrays in  **A** .

**Example Input**
Input 1:

```txt
A = [  [1, 2, 3]
        [2, 4, 6]
        [0, 9, 10]
     ]
```

**Example Output**
Output 1:

```txt
[0, 1, 2, 2, 3, 4, 6, 9, 10]
```

**Example Explanation**
Explanation 1:

```txt
You need to merge [1, 2, 3] , [2, 4, 6] and [0, 9, 10]  into a single array
 so the merged array will look like [0, 1, 2, 2, 3, 4, 6, 9, 10]
```

##### 2.4.1.2 问题解析

该题目的解法可以参考上面的[合并 k 个排序链表](#2-合并-k-个排序的链表)。

##### 2.4.1.3 参考代码

```java
/**
 * 合并 k 个有序数组
 * @param A 有序数组
 * @return 合并后的数组
 */
public int[] mergeKArrays(int[][] A) {
    return mergeK(A, 0, A.length - 1);
}

/**
 * 递归合并 k 个有序数组
 * @param a 有序数组
 * @param left  合并数组的左下标
 * @param right 合并数组的右下标
 */
public int[] mergeK(int[][] a, int left, int right) {
    if (left > right) {return new int[]{};}
    if (left == right) {return a[left];}    //  中间一个的情况，直接返回这个数组
  
    int mid = (left + right) / 2;
    return merge(mergeK(a, left, mid), mergeK(a, mid + 1, right));  //  从中间分成两段，再将合并好的两段合并
}

/**
 * 合并两个有序数组（采用创建一个新数组的方式）
 * @param a 第一个数组
 * @param b 第二个数组
 */
public int[] merge(int[] a, int[] b) {
    int[] arr = new int[a.length + b.length];
    int i = 0, j = 0, ind = 0;
  
    while (i < a.length && j < b.length) {
        if (a[i] < b[j]) {arr[ind++] = a[i++];}
        else {arr[ind++] = b[j++];}
    }
  
    if (i <= a.length - 1) {
        while (i < a.length) {arr[ind++] = a[i++];}
    }
  
    if (j <= b.length - 1) {
        while (j < b.length) {arr[ind++] = b[j++];}   
    }

return arr;
}
```

## 参考文献

1. [21. 合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists)。
2. [23. 合并 K 个升序链表](https://leetcode.cn/problems/merge-k-sorted-lists)。
3. [合并 k 个已排序的链表](https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=117&tqId=37747&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26pageSize%3D50%26search%3D%25E9%2593%25BE%25E8%25A1%25A8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&difficulty=undefined&judgeStatus=undefined&tags=&title=%E9%93%BE%E8%A1%A8)。
4. [88. 合并两个有序数组](https://leetcode.cn/problems/merge-sorted-array)。
5. [Merge K sorted arrays!](https://www.interviewbit.com/problems/merge-k-sorted-arrays)