단일 링크 된 목록에서 마지막 요소를 찾는 방법은 무엇입니까?

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 List가 될 것이지만, 마지막 노드를 찾는데 O(n=1)을 피할 것입니다.