LeetCode合并两个有序链表代码超时问题排查求助

你的代码逻辑本身是正确的，但存在一个容易引发潜在问题的设计，在特定输入场景下可能导致返回循环链表，进而触发LeetCode判题系统的超时（判题时会遍历结果链表，遇到循环则无法终止）。

问题根源 #

你通过创建两个哨兵节点l1、l2包裹输入链表，操作时依赖l1.next和l2.next访问原链表节点。这种写法本身没问题，但当循环仅移动其中一个哨兵的指针时，另一个哨兵仍指向初始的哨兵节点，其next始终保留着原链表的头引用。

举个极端场景：

• 输入list1 = new ListNode(1)，list2 = new ListNode(1)（两个独立的单节点链表）
• 循环中因值相等走else分支，l2移动到list2的节点，l1仍停留在初始哨兵节点，l1.next始终指向list1的节点
• 循环结束后，l2.next为null，触发if (!l2.next)，将l.next设为l1.next（即list1的节点）
• 此时结果链表为dummy -> list2节点 -> list1节点，本身没问题；但如果输入的list1和list2是同一个节点（虽然LeetCode测试用例不会出现，但手动构造这种输入时），就会形成list2节点.next = list2节点的循环链表，导致判题时无限遍历超时。

为什么直接操作原链表的写法不会有这个问题 #

他人的写法直接用list1、list2作为遍历指针，每次循环移动的是原链表的节点指针，不存在“哨兵节点保留原链表头引用”的情况，自然不会出现上述潜在风险。

修正后的代码 #

你可以保留哨兵节点的设计，但调整遍历指针的初始化方式，直接指向原链表节点，避免额外的哨兵包裹：

/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  if (!list1) return list2;
  if (!list2) return list1;
  const dummy = new ListNode(0);
  let l = dummy;
  let l1 = list1; // 直接指向原链表节点
  let l2 = list2;
  while (l1 && l2) { // 直接判断节点是否存在
    if (l1.val < l2.val) {
      l.next = l1;
      l1 = l1.next;
    } else {
      l.next = l2;
      l2 = l2.next;
    }
    l = l.next;
  }
  // 直接拼接剩余节点，无需两次判断
  l.next = l1 || l2;
  return dummy.next;
};

原代码的快速修复方案 #

如果你坚持使用哨兵包裹的写法，只需替换原代码末尾的两个if语句，确保拼接剩余链表的逻辑更简洁可靠：

// 替换原代码末尾的两个if语句
l.next = l1.next || l2.next;

这样无论l1、l2是否停留在初始哨兵节点，都能正确拼接剩余的链表部分，避免潜在的循环风险。

内容的提问来源于stack exchange，提问作者Meow_0w0