如何查找單鏈表中的最後一個元素？

Question

在單向鏈表中，我們知道最後一個節點的下一個節點指向null，以便我們可以通過遍歷找出它。

如果單鏈表的最後一個節點指向某個中間節點，那麼我們如何才能找到最後一個節點？

Answer 1

如果「最後一個節點」指向某個其他節點，那麼它不是真正的最後一個節點，是嗎？更不用說這會拉長並可能破壞普遍接受的「清單」的定義。

通常找到你會做一些這樣

Node *current = list.start, 
    *next = current.next; 

while (next != null) 
{ 
    current = next; 
    next = current.next; 
} 

print("Last node is " + current->value); 

但是最後一個元素，這是假定你的「最後一個節點」不實際指向空。否則，你會陷入無限循環。

通常是好做法，以保持一個指針列表的最後一個節點，以及第一，所以這是一種不依賴指向空的最後一個節點上一個簡單的解決方案。

Answer 2

嗯，我想放一個「is_visited」布爾值節點將滿足就好：

//make sure the counters of all nodes are 0 
cur=head_node 
cur->visit=1 
while(cur->next!=null AND cur->next->visit==0) { 
    cur=cur->next 
    cur->visit=1 
} 
//cur points to the last node 

Answer 3

即使你可以使用一個尾指針單鏈表。它仍然是單鏈表，但它避免了O(n=1)找到最後一個節點。