合并两个升序链表与合并 K 个升序链表

合并两个升序链表

给定两个升序排列的单链表，要求合并成一个新的升序链表并返回头节点。这道题是链表合并的入门题型，掌握它的核心逻辑，才能轻松应对后续的 k 个链表合并。

解题关键：3 个核心设计

想要优雅解决这道题，离不开三个关键设计，少一个都可能让边界处理变得繁琐：

• 哨兵节点（dummy）：值通常设为 -1（无实际意义），作用是简化边界处理。比如当两个链表都为空、或其中一个为空时，不用单独判断头节点，直接返回 dummy.next 即可。
• 动态指针（cur）：初始指向哨兵节点，相当于拼接工人，负责把选中的节点接在新链表后面，每拼接一个节点就向后移动一步。
• 双指针（p1、p2）：分别指向两个链表的当前遍历节点，是决策核心。通过比较 p1.val 和 p2.val，决定该拼接哪个节点，直到其中一个链表遍历完毕。

具体执行逻辑：① 双指针同步遍历，while 循环条件是 p1 和 p2 都不为空；② 若 p1.val ≤ p2.val，把 p1 接在 cur.next，同时 p1 后移；反之则拼接 p2，p2 后移；③ 每轮循环结束后，cur 后移一步，准备接下一个节点；④ 循环结束后，必有一个链表还有剩余节点（本身有序），直接把剩余链表接在 cur.next 即可，无需逐个遍历。

JavaScript 实现

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *   this.val = (val===undefined ? 0 : val)
 *   this.next = (next===undefined ? null : next)
 * }
 */
/**
 * 合并两个升序有序链表，返回新的升序链表头节点
 * @param {ListNode} list1 - 第一个升序有序链表头节点
 * @param {ListNode} list2 - 第二个升序有序链表头节点
 * @returns {ListNode} 合并后的升序链表头节点
 */
var mergeTwoLists = function (list1, list2) {
  // 哨兵节点（哑节点）：简化空链表等边界情况处理
  let dummy = new ListNode(-1);
  // 动态指针：负责拼接新节点，初始指向哨兵节点
  let cur = dummy;
  // 双指针：分别遍历两个输入链表
  let p1 = list1, p2 = list2;

  // 双指针同步遍历，直到其中一个链表遍历完毕
  while (p1 !== null && p2 !== null) {
    if (p1.val <= p2.val) {
      // 拼接 p1 节点，p1 指针后移
      cur.next = p1;
      p1 = p1.;
    }  {
      
      cur. = p2;
      p2 = p2.;
    }
    
    cur = cur.;
  }

  
  cur. = p1 !==  ? p1 : p2;
  
   dummy.;
};