如何查找单链表中的最后一个元素

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);

然而，这假设您的"最后一个节点"确实指向null。否则，你将陷入一个无限循环。

通常，将指针保持为列表的最后一个节点和第一个节点是一种很好的做法，因此这是一种不依赖于最后一个指向null的节点的琐碎解决方案。

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

即使在Singly Linked列表中，也可以使用Tail指针。它仍然是一个Singly链表，但它在查找最后一个节点时避免了O(n=1)。

Answer 4

简单地遍历并满足指向空的最后一个条件

void printlast(Node* n){
    while(n!=NULL){
        n=n->next;
        if(n->next==NULL){
            cout<<n->data<<" ";
        }
    }
}