尋找鏈表倒數第K個結點演算法好壞是否取決於遍歷次數？

題目的意思是有個單鏈表，結點信息，只有data和next指針。

先在只提供一個首元結點，設計一個演算法，怎樣開銷最少找到倒數第K個結點。

我看了下答案，是讓兩個指針移動，當這兩個指針相差K個結點的時候，同時移動，這樣到底的時候，上一個結點就是所求結點。只需遍歷一次。不過我覺得，如果K比總結點的一半還多。是不是開銷要比下面這個演算法還要大。 先遍歷所有節點，記錄總數，再找到那個結點（total-K個）。假如指針讀寫都算一次運算。考慮到兩個指針。

//添加考研題滿分答案解釋

//題目

---

兩個指針移動顯然就等於讀兩遍啊，所以為什麼不先讀一篇算長度然後讀第二遍？這還保證不出問題。

---

參考答案竟然故意卡循環兩遍，如果是出題人原意，只能說出題人水平太次了，以他的水平根本認識不到兩種方法其實是一樣的。

試圖考研後來放棄的學渣表示同情考研的學霸們，你們真心不容易，連這種根本狗屁不通的解釋你們都要使勁的開腦洞去理解..

---

這題目性能好壞取決於比較次數和賦值次數。

(問題中)一次遍歷的做法中，比較了2n次，指針賦值2n-k次；兩次遍歷的做法中，比較了2n-k次，賦值了2n-k次。所以兩次遍歷實際上更高效率。(Update: 其實是問題中書本的答案寫砸了， 一次遍歷確實可以做到效率更高，下面會說明).

附兩次遍歷的實現：

ListNode *findKth(ListNode* head, int k) {
int count = 0;
for(ListNode* p=head; p; p = p-&>next)
count ++;
for(count -= k; count &> 0; count--)
head = head-&>next;
return head;
}


實際上，一次遍歷可以這樣寫，將比較次數減少到 n 次。這樣的話效率就比上面的方法(2n - k &>= n)高了。

一次遍歷的實現：

ListNode *findKth2(ListNode *head, int k) {
assert(k &>= 0);
ListNode* p = head;
while(k--) p = p-&>next; // or while(p k--) ...
while(p) {
head = head-&>next;
p = p-&>next;
}
return head;
}


---

演算法時間複雜度一樣，但實際應用中一次遍歷快，雙指針可以充分利用寄存器，鏈表各結點內存定址次數少12。

用彙編實現一遍就理解好在哪裡了

---

我只是來吐槽的，做王道單科的時候被這個神奇的滿分答案當場嚇尿了。弱校考研狗不能再慘。

---

去年面愛奇異時候就是被這道題掛了。。。。

我回答是先遍歷一次求長度，然後再遍歷一次就可以了。。那個面試官說你這效率太低，只需要2個指針差k步同時啟動即可，一遍即可。我說那不也是O(2N)複雜度嗎？然後就沒有然後了。。

---

之前在手機上沒看到圖片，題目里已經說過遞歸的問題了。以下作廢！

------------------------------------------------------------------------------------

正確答案怎麼可能不是遞歸？雖然雙指針看上去有點小聰明。

---

雙指針能用上cache啊，遍歷兩次怎麼就比雙指針好了，面試的時候寫出來這麼平凡的答案好意思嗎（

當然這書寫得狗屁不通就是了

---

推薦閱讀：