题目：

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

示例：

示例一：

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

示例二：

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

示例三：

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

提示：

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

思路

假设有一条没有串球的红绳子，还有两条串着标有数字的球的链，每条链上球的标号都是从小到大依次递增的，每次从这两条链中选择一个数字最小的球串在红绳子上，当所有的球都串到红绳子上时，这条红绳子上的所有球上标的数字就是有序的了。

这个问题的关键就在于如何选择数字最小的球。这两条链中各自最小的球都在最前面，但是不能确定哪条链中最小的数字更小，所以就要比较两条链中数字最小的球哪一个更小，并将其接到绳子上，这样一个球的顺序就排好了。因为上一轮比较已经将数字最小的球接在了红绳子上，因此不能重复选择。所以需要选择这条链的下一个球，也就是数字第二小的球与另一条链上数字最小的球比较，再选出两者之间数字较小的球接在绳子上。依次类推，直到其中一条链上的所有球都被接在红绳子上了，这样这条链已经没有球可以比较了。

此时有可能另外一条链中还有部分球没有串到红绳上，但是可以确定的是，这条绳上的所有球都应该比最后一个被串到红绳上的球的数字大。因为只有当前链中选择的球比另一条链中的小才会该表选择到下一个球，才会先走到末尾。所以接下来只用将没有走完的那条链拼接到红绳上就完成了。

将上述的步骤用在链表上就可以概括为：

1. 初始化指向两条链中指向未添加到新链的最小节点的指针。
2. 比较当前两个链表中最小的节点。
3. 然后将较小的节点拼接到当前已排序链表的最后一个节点后面。
4. 然后再迭代值向较小的节点的指针和指向已排序链表的最后一个节点的指针，迭代的方式都是向后移动一个节点。
5. 重复上述两个步骤，直到两个链的指针中有一个指向 null。
6. 拼接未遍历完的节点。
7. 返回新链表的头节点指针 。

步骤图解

1. 初始状态

2. 对比 p1.val 与 p2.val，将两条链表中更小的节点拼接到新链表。

3. 指针迭代，newList，p2 指针均向后移动一个节点。

4. 重复步骤 2。

5. 重复步骤 3。

6. 重复步骤 2。

7. 重复步骤 2。

8. 重复步骤 3。

9. 重复步骤 2。

10. 重复步骤 3。

11. 重复步骤 2。

12. 重复步骤 3。

13. 到达链表末尾，退出循环，拼接未遍历完节点。

14. 返回 dummy 的下一个节点

递归解法

这道题还有递归的解法，其实思路都一是相同的，只是缩减问题规模的方式不同。迭代方式的重复操作是放在循环里，而递归方式的重复操作则是放在函数中，每次递归的函数调用都相当于执行依次迭代方式中的循环体中的代码。递归方式的变量迭代通过参数传递和函数的返回值实现，而迭代方式则是直接为局部变量赋值。递归方式需要对不同的分支传递不同的参数，副作用和返回值也不同。细节直接看代码实现就能理解了。

注意

• 其中一条链表遍历完之后就应该停止循环。
• 将没有遍历完的链表从当前的节点开始拼接到新链表。
• 使用 dummy 节点让所有的节点以相同的方式处理，而不用对首节点特殊处理。
• 熟练链表的操作。

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

迭代解法

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummyNode = new ListNode()
    let [p1, p2, newList] = [l1, l2, dummyNode];
    while (p1 && p2) {
        newList.next = p1.val < p2.val ? p1 : p2; // 比较，拼接
        (p1.val < p2.val) ? (p1 = p1.next) : (p2 = p2.next); // 指针迭代
        newList = newList.next; // 指针迭代
    }
    newList.next = p1 || p2;
    return dummyNode.next;
};

递归解法

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  if(l1 && l2){
      if(l1.val < l2.val){
          l1.next = mergeTwoLists(l1.next, l2)
          return l1;
      } else {
          l2.next = mergeTwoLists(l1, l2.next)
          return l2;
      }
  } else {
      return l1 || l2 // 到达一条链的末尾，返回另一条链中的当前遍历到的节点
  } 
};

相关阅读

• 206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)