我一直在經歷 LeetCode 上的演算法挑戰，剛剛完成了“從串列末尾洗掉第 N 個節點”。
許多頂級答案聲稱找到了“一次性”解決方案，我在下面包含了一個 Java 示例。
請有人解釋為什么“while(n-->0) h2=h2.next;” 不算作鏈表的額外傳遞，因此，使其成為“兩次傳遞”解決方案？
public ListNode RemoveNthFromEnd(ListNode head, int n) {
ListNode h1=head, h2=head;
while(n-->0) h2=h2.next;
if(h2==null)return head.next; // The head need to be removed, do it.
h2=h2.next;
while(h2!=null){
h1=h1.next;
h2=h2.next;
}
h1.next=h1.next.next; // the one after the h1 need to be removed
return head;
}
我查看了對此和其他解決方案的評論，但找不到答案。同樣，一般的谷歌搜索也沒有給出解釋。
提前致謝。
uj5u.com熱心網友回復：
不，這不是一次性通過。One-pass 是相對于順序 I/O 機制（典型的磁帶）定義的，意味著每條資料最多按順序讀取一次。將鏈表類比為此處的磁帶，該演算法不是一次性的，因為一般來說，某些節點的next欄位將被h2=h2.next（在任一回圈中）讀取一次，并h1=h1.next在第二個回圈中再次被讀取。
uj5u.com熱心網友回復：
該演算法不是單通的，但不是因為第一個回圈。
第一個回圈對n元素執行部分傳遞。
第二個回圈對l-n元素執行兩個同時部分傳遞（h2與第一個回圈中的元素互補）。總之，欄位的2l-n查找next。
可以在長度為 的 FIFO 佇列的幫助下實作單通道解決方案n，但這“隱藏”了部分通道。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/347692.html
上一篇：專案在網格上的可重復隨機放置
下一篇：在棋盤上移動N個國王