CODEWITHSUNDEEP
pointerslinked-list
mlstudent
mlstudent

Reputation: 948

Finding end of linked list

I'm looking over interview questions, and I came across "How do you find out if a linked-list has an end? (i.e. the list is not a cycle)." It gives a solution (traverse it one and two nodes at a time, and see if the pointers are ever equal).

Couldn't we just keep the pointer that we start at and see if while traversing it, we ever hit that pointer again? Or will that not work?

Upvotes: 0

Views: 766

Answers (3)

sr01853
sr01853

Reputation: 6121

Couldn't we just keep the pointer that we start at and see if 
while traversing it, we ever hit that pointer again?

No. See the below case. You will just traverse the loop without ever hitting the start node of the list

Cycle

Another way to find if there is a loop:

If you reverse the list, and remember the inital node, you will know that there is a cycle if you get back to the first node. While efficient, this solution changes the list and not suited for multithreaded applications.

Upvotes: 0

Vijay
Vijay

Reputation: 67211

Take two pointers one should traverse the list one node at a time and another should traverse the list 2 nodes at a time. if at any point of time they meet each other(both the pointers refer to the same node).It means its a circular linked list and does not have an end.

Upvotes: 0

mickeyt
mickeyt

Reputation: 406

That will not work: the linked list may contain a cycle that does not include the first pointer.

Keep in mind that a node in a linked list can be linked to by more than one other node!

Upvotes: 2

Related Questions