LeetCode 23. 合并K个升序链表算法调试求助

我完全理解你想从自己的思路出发修正问题的想法，咱们一起来拆解你的代码里的问题根源：

核心问题分析 #

你的算法思路是对的：每次从所有链表的当前头节点中选最小的，把它加入结果链表，然后将对应链表的头节点后移。但代码里有两个关键错误导致了重复出现1的异常：

1. 复用原链表节点破坏了原链表结构

你直接把原链表的节点链接到结果链表中，这会修改原链表节点的next指针（结果链表的最后一个节点是原链表中的某个节点，它的next会被指向新选中的节点）。比如：

• 当你把第一个链表的4节点作为结果链表的节点后，又把它的next指向第二个链表的1节点，这就破坏了第一个链表原本的4->5结构，变成了4->1。
• 后续执行lists[0] = lists[0].next时，lists[0]就会指向第二个链表的1节点，而不是原本的5节点，这就导致了重复处理1，还丢失了5节点。

2. index变量未正确初始化

index在函数顶部声明但未初始化，当某次循环中所有链表都已遍历完毕（所有lists[i]都是null），index会保留上一次的旧值，可能导致访问无效的链表节点。

修正方案 #

保持你的核心思路不变，只需要做两处关键修改：

1. 创建新节点构建结果链表：不再复用原链表节点，而是根据选中的最小值创建新的ListNode，这样不会破坏原链表的结构。
2. 初始化index并增加空链表判断：每次循环开始时重置index，遍历链表时直接跳过空链表，避免无效判断。

修改后的代码 #

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  let head: ListNode | null = null;
  let temp: ListNode | null = null;
  let min: number;
  let index: number | null = null; // 初始化为null，避免旧值干扰

  // 修改setVal：接收值，创建新节点
  function setVal(val: number): void {
    const newNode = new ListNode(val);
    if (temp === null) {
      temp = newNode;
    } else {
      temp.next = newNode;
    }
    if (!head) {
      head = temp;
    }
    temp = temp.next;
  }

  do {
    min = Number.MAX_SAFE_INTEGER;
    index = null; // 每次循环重置index
    const map: (number | undefined)[] = []; // 调试用map

    for (let i = 0; i < lists.length; i++) {
      const currentNode = lists[i];
      if (!currentNode) {
        map.push(undefined);
        continue; // 跳过空链表
      }
      const currentVal = currentNode.val;
      map.push(currentVal);
      if (currentVal < min) {
        min = currentVal;
        index = i;
      }
    }

    // 只有找到有效节点时才处理
    if (index !== null && lists[index]) {
      setVal(min);
      lists[index] = lists[index].next;
    }

    console.log(min, map); // 调试输出
  } while (min < Number.MAX_SAFE_INTEGER);

  return head;
};

// 假设ListNode定义如下（如果环境未提供）
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);
  }
}

验证修正效果 #

用你的测试输入[[1,4,5],[1,3,4],[2,6]]测试，现在的循环过程会正确遍历所有节点，不会出现重复的1，最终得到正确的合并结果1->1->2->3->4->4->5->6。

这样修改后，既保留了你原本的算法思路，又解决了结构破坏和变量初始化的问题，应该能正常运行了。

内容来源于stack exchange