我正在嘗試排序鏈表的 leetcode 合并
我剛剛發現我放在list1 = list1.next. 之前的代碼有一個錯誤result.next = list1，導致代碼導致無限回圈。但是，我試圖追蹤但仍然不明白邏輯是如何導致無限回圈的。
錯誤的解決方案
// Loop until list1 and list2 is not empty
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
list1 = list1.next;
result.next = list1;
} else {
list2 = list2.next;
result.next = list2;
}
System.out.println(list2.val);
result = result.next;
}
正確的解決方案
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
result.next = list1;
list1 = list1.next;
} else {
result.next = list2;
list2 = list2.next;
}
System.out.println(list2.val);
result = result.next;
}
有人能告訴我為什么list1 = list1.next和list2 = list2.next的放置會導致無限回圈嗎？這是我的除錯嘗試
可以看到兩張圖，表示結果linkedlist的值，會不斷回圈遍歷4,2,3 -> 2,4,2 -> 4,2,3 -> 2,4,2的值.... 反之亦然。
最后這是我的輸入 1,2,4 1,3,4
uj5u.com熱心網友回復：
當您逐步在一張紙上繪制串列節點的狀態時，您將看到該回圈是如何引入的。
這是一個可視化 - 一步一步。我假設代碼首先創建了一個虛擬節點，該節點也result有一個參考。在回圈執行之前，我們因此具有以下狀態：
list1
↓
┌───┐ ┌───┐ ┌───┐
│ 1 ├──?│ 2 ├──?│ 4 ├──? null
└───┘ └───┘ └───┘
list2
↓
┌───┐ ┌───┐ ┌───┐
│ 1 ├──?│ 3 ├──?│ 4 ├──? null
└───┘ └───┘ └───┘
result
↓
┌───┐
│ ├──? null
└───┘
↑
dummy
回圈的迭代1if ：條件為假，所以list2被移動，然后result->next得到相同的參考，然后result自己移動：
list1
↓
┌───┐ ┌───┐ ┌───┐
│ 1 ├──?│ 2 ├──?│ 4 ├──? null
└───┘ └───┘ └───┘
list2
↓
┌───┐ ┌───┐ ┌───┐
│ 1 ├──?│ 3 ├──?│ 4 ├──? null
└───┘┌─?└───┘ └───┘
│ ↑
┌───┐│ result
│ ├┘
└───┘
↑
dummy
回圈的迭代2if ：條件為真，所以list1被移動，然后result->next得到相同的參考，然后result自己移動：
list1
↓
┌───┐ ┌───┐ ┌───┐
│ 1 ├──?│ 2 ├──?│ 4 ├──? null
└───┘┌─?└───┘ └───┘
│ ↑
│ result
└───────┐
list2│
↓ │
┌───┐ ┌───┐│ ┌───┐
│ 1 ├──?│ 3 ├┘ │ 4 ├──? null
└───┘┌─?└───┘ └───┘
│
┌───┐│
│ ├┘
└───┘
↑
dummy
此時我們已經遇到了一個嚴重的問題，因為屬于第二個串列的最后一個節點現在已經分離并且無法訪問。
回圈的第3 次迭代if：條件為真，因此list1被移動，然后result->next獲得相同的參考（但情況已經如此），然后result自身移動：
list1
↓
┌───┐ ┌───┐ ┌───┐
│ 1 ├──?│ 2 ├──?│ 4 ├──? null
└───┘┌─?└───┘ └───┘
│ ↑
│ result
└───────┐
list2│
↓ │
┌───┐ ┌───┐│ ┌───┐
│ 1 ├──?│ 3 ├┘ │ 4 ├──? null
└───┘┌─?└───┘ └───┘
│
┌───┐│
│ ├┘
└───┘
↑
dummy
回圈的第4 次迭代if：條件為假，因此list2被移動（并且走錯了路！），然后result->next獲得相同的參考（創建回圈！），然后result自身移動：
list2 list1
↓ ↓
┌───────────────┐
┌───┐└─?┌───┐ ┌───┐│
│ 1 ├──?│ 2 ├──?│ 4 ├┘
└───┘┌─?└───┘ └───┘
│ ↑
│ result
└───────┐
┌───┐ ┌───┐│ ┌───┐
│ 1 ├──?│ 3 ├┘ │ 4 ├──? null
└───┘┌─?└───┘ └───┘
│
┌───┐│
│ ├┘
└───┘
↑
dummy
現在回圈已經完成！值為 2 的節點指向值為 4 的節點，反之亦然！
uj5u.com熱心網友回復：
在回答之前需要查看所有相關的代碼檔案，但我觀察到你正在做
System.out.println(list2.val);
您在這里假設 list2!=null
while (list1 != null && list2 != null)
但在你正在做的代碼中
list2 = list2.next;
}
System.out.println(list2.val);
如果 list2 在這里變為空怎么辦。需要進行空檢查
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/524611.html