Merge Two Sorted Lists（合并两个有序链表）

题目 / Problem

中文： 给定两个升序链表的头节点 list1 和 list2，请将它们合并为一个升序链表。新链表由拼接两个原链表中的节点组成。

返回合并后链表的头节点。

English: You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

示例 / Examples

Example 1

Input:  list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]

Example 2

Input:  list1 = [], list2 = []
Output: []

Example 3

Input:  list1 = [], list2 = [0]
Output: [0]

约束 / Constraints

• 两个链表的节点总数在 [0, 50] 范围内。
  The total number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• list1 和 list2 均按非递减顺序排列。
  Both list1 and list2 are sorted in non-decreasing order.

解题思路：迭代 / Approach: Iteration

使用一个哑节点 dummy 作为结果链表的固定起点，并使用指针 current 指向结果链表的末尾。
Use a dummy node dummy as the fixed starting point of the result and a pointer current to track its tail.

1. 当两个链表都不为空时，比较它们当前节点的值。
   While both lists are non-empty, compare the values of their current nodes.
2. 将值较小的节点接到 current 后面，并向后移动对应链表的指针。
   Append the smaller node after current, then advance the corresponding list pointer.
3. 每次拼接后，将 current 向后移动一位。
   Move current forward after each append operation.
4. 当一个链表遍历完后，直接接上另一个链表的剩余部分。
   When one list is exhausted, append the remaining part of the other list.
5. 返回 dummy.next，跳过辅助的哑节点。
   Return dummy.next, skipping the helper dummy node.

题目要求复用原链表中的节点，因此无需为每个值创建新节点。
The problem asks us to splice the original nodes together, so no new node is needed for each value.

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *   this.val = val ?? 0;
 *   this.next = next ?? null;
 * }
 */

/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
function mergeTwoLists(list1, list2) {
  const dummy = new ListNode(0);
  let current = dummy;

  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      current.next = list1;
      list1 = list1.next;
    } else {
      current.next = list2;
      list2 = list2.next;
    }

    current = current.next;
  }

  current.next = list1 ?? list2;
  return dummy.next;
}

执行过程 / Walkthrough

以 list1 = [1, 2, 4]、list2 = [1, 3, 4] 为例：
For list1 = [1, 2, 4] and list2 = [1, 3, 4]:

此时 list1 已遍历完，直接接上 list2 剩余的 [4]，得到 [1, 1, 2, 3, 4, 4]。
At this point, list1 is exhausted. Append the remaining [4] from list2 to obtain [1, 1, 2, 3, 4, 4].

复杂度 / Complexity

设两个链表的节点数分别为 m 和 n。
Let the two lists contain m and n nodes respectively.

• 时间复杂度：O(m + n)，每个节点最多处理一次。
  Time: O(m + n), because each node is processed at most once.
• 空间复杂度：O(1)，只使用了常数个额外指针。
  Space: O(1), because only a constant number of extra pointers is used.

递归解法 / Recursive Approach

每次选择头节点值较小的链表，并递归合并其剩余部分与另一个链表。
At each step, choose the list with the smaller head value and recursively merge its remainder with the other list.

function mergeTwoListsRecursive(list1, list2) {
  if (list1 === null) return list2;
  if (list2 === null) return list1;

  if (list1.val <= list2.val) {
    list1.next = mergeTwoListsRecursive(list1.next, list2);
    return list1;
  }

  list2.next = mergeTwoListsRecursive(list1, list2.next);
  return list2;
}

• 时间复杂度 / Time: O(m + n)
• 空间复杂度 / Space: O(m + n)，递归调用会占用调用栈。
  Recursive calls use the call stack.

易错点 / Common Pitfalls

• 返回值应为 dummy.next，而不是辅助节点 dummy。
  Return dummy.next, not the helper node dummy.
• 拼接节点后，别忘了移动 current 和被选中链表的指针。
  After appending a node, remember to advance both current and the selected list pointer.
• 循环结束后，要将未遍历完的链表整体接到结果末尾。
  After the loop, append the entire remainder of the non-empty list.
• 输入链表可能为空，应正确处理 null。
  Either input list may be empty, so handle null correctly.
• 这里复用并重新连接原有节点，不需要逐个复制节点。
  Reuse and reconnect the original nodes instead of copying them one by one.