how can I find last node of a circular linked list whose size I dont know and the last node points to any other node except first node of the linked list?

Question

how can I find last node of a circular linked list whose size I dont know and the last node points to any other node except first node of the linked list?

Answer 1

By definition, if a node does not point to the first node of a circular linked list,
it is not the last node.

Can you elaborate here?

Answer 2

Maybe add parameter to nodes of the list which tells you if you at end? I think, it wouldn't be problem.

Otherwise, you can remember nodes you already visted. When the next node is already visited, you are at the end.

Answer 3

A strange list... why would you ever need something like this? But anyway...

You can simply iterate over all nodes, and stop as soon as the next node would be one you have already visited. The current node will then be your answer.

You need some way to keep track of which nodes have been visited. Add a boolean flag to each node, or use some kind of set data type with fast insertion and lookup (e.g. a hash set).

Answer 4

One algorithm that can be used for this is the Floyd cycle algorithm.

Also, see this question.

Answer 5

The Floyd cycle algorithm won't give the last element of the list. It will only tell if there is a cycle or not.

The definition of the last one would be that, while traversing the list in a sequential scan starting from the first one, all elements before it and the last one aren't seen before (pointer value). The after last one will be the first element that has already been seen in this sequential scan.

An easy solution is to flag visited elements so an element already seen is easily detected. The flag may be intrusive, i.e. by changing a bit in the element, or external by using a hash table to store pointer values.

Since we need to be able to test if an element has already been visited, I don't see another solution.