提问人：Meow_0w0 提问时间：7/21/2023 最后编辑：Meow_0w0 更新时间：7/22/2023 访问量：70
leetcode JavaScript 合并两个排序列表
leetcode JavaScript Merge Two Sorted Lists
问：
我想知道为什么我的代码超时了，当我在 leetcode 中解决这个问题时，我认为这是导致它的 while 循环的条件，但有人可以告诉我为什么吗？ 我尝试使用 chatGPT，但它无法给出确切的答案。
我想这可能是因为我做了一个无休止的循环。我看了别人的答案，发现他们在while循环的条件和内容中使用了ListNode本身，而我用的是ListNode.next，我理解了他们的方法，但仍然不知道为什么我的方法不起作用。
/**
* @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 = new ListNode(0);
let l2 = new ListNode(0);
l1.next = list1;
l2.next = list2;
while (l1.next && l2.next) {
if (l1.next.val < l2.next.val) {
l.next = l1.next;
l1 = l1.next;
} else {
l.next = l2.next;
l2 = l2.next;
}
l = l.next;
}
if (!l1.next) l.next = l2.next;
if (!l2.next) l.next = l1.next;
return dummy.next;
};
答：
0赞
trincot
7/22/2023
#1
让我们以以下输入为例：
list1 = [1, 3]
list2 = [2, 4]
我们可以可视化循环即将开始时的状态。此时，已经创建了三个虚拟节点，分别由 （和 ） 引用，并且：dummyll1l2
dummy l
↓ ↓
┌────────────┐
│ val: 0 │
│ next: null │
└────────────┘
l1 list1
↓ ↓
┌────────────┐ ┌────────────┐ ┌────────────┐
│ val: 0 │ │ val: 1 │ │ val: 3 │
│ next: ────────►│ next: ────────►│ next: null │
└────────────┘ └────────────┘ └────────────┘
┌────────────┐ ┌────────────┐ ┌────────────┐
│ val: 0 │ │ val: 2 │ │ val: 4 │
│ next: ────────►│ next: ────────►│ next: null │
└────────────┘ └────────────┘ └────────────┘
↑ ↑
l2 list2
迭代 1
在第一次迭代中，条件为 true，在块中的两个赋值和最终赋值执行后，我们有这个：ififl = l.next
dummy
↓
┌────────────┐
│ val: 0 │
│ next: ──────────┐
└────────────┘ │
│ list1 l1 l
│ ↓ ↓ ↓
┌────────────┐│ ┌────────────┐ ┌────────────┐
│ val: 0 │└─►│ val: 1 │ │ val: 3 │
│ next: ────────►│ next: ────────►│ next: null │
└────────────┘ └────────────┘ └────────────┘
┌────────────┐ ┌────────────┐ ┌────────────┐
│ val: 0 │ │ val: 2 │ │ val: 4 │
│ next: ────────►│ next: ────────►│ next: null │
└────────────┘ └────────────┘ └────────────┘
↑ ↑
l2 list2
第二个虚拟节点（最初被引用的节点）不再有引用，因此可以对其进行垃圾回收。没关系。l1
迭代 2
在第二次迭代中，我们将 3 与 2 进行比较，因此执行了该块。当它的两个任务和最终任务执行完毕后，我们得到：elsel = l.next
dummy
↓
┌────────────┐
│ val: 0 │
│ next: ──────────┐
└────────────┘ │
│ list1 l1
│ ↓ ↓
│ ┌────────────┐ ┌────────────┐
└─►│ val: 1 │ │ val: 3 │
│ next: ──┐ │ │ next: null │
└─────────│──┘ └────────────┘
┌────────────┘
┌────────────┐│ ┌────────────┐ ┌────────────┐
│ val: 0 │└─►│ val: 2 │ │ val: 4 │
│ next: ────────►│ next: ────────►│ next: null │
└────────────┘ └────────────┘ └────────────┘
↑ ↑ ↑
list2 l2 l
在这里，我们看到第一个问题：值为 3 的节点已成为孤立节点！不再引用它，因此它永远丢失了（它可以被垃圾收集）。在下一次迭代中，我们也可以省略另一个虚拟节点（最初由 ） 引用。但问题会越来越多......l2
迭代 3
在此迭代中，我们不再具有值为 3 的节点。现在比较在 2 和 4 之间，因此块执行。块中的第一个语句创建一个循环：因为与 相同。我们可以在那里停止分析，因为这个循环将导致变量 ，并卡在那个循环中：ififl.next = l1.nextl1.nextlll1l2
dummy
↓
┌────────────┐
│ val: 0 │
│ next: ──────────┐
└────────────┘ │
│ list1 l1
│ ↓ ↓
│ ┌────────────┐
└─►│ val: 1 │
│ next: ──┐ │
└─────────│──┘
┌────────────┘
│ ┌────────────┐ ┌────────────┐
└─►│ val: 2 │◄─┐│ val: 4 │
│ next: ────────┘│ next: null │
└────────────┘ └────────────┘
↑ ↑ ↑
list2 l2 l
代码中的主要问题是，您没有保留列表中已经合并的部分并排在前面。正确的方法是拥有并引用两个仍未更改（未合并）的输入列表，并且应引用合并部件的尾部。因此，我们在上面看到的，同一列表的位置和引用节点，永远不应该发生。l1l2l1l2ll1l2
正如您已经知道正确的代码一样，我将就此结束。我希望它能澄清出了什么问题。
评论