How to find the middle node of a single linked lis

Question

I have a problem statement like: "How to find the middle node of a singly linked list in only one traversal, and the twist is we don't know the number of nodes in the linked list?"

I have an answer like "take a vector and start pushing all the nodes' addresses as and when you are traversing the linked list and increment a counter till you reach the end of the list". So at the end we can get the number of nodes in the list and if even (counter/2) or if odd (counter/2 + counter%2) gives the middle node number and with this we can get vectore.at(middlenodenumber) points to the middle node".

This is fine...but this is waste of memory storing all the address of a very large linked list! So how can we have a better solution?

Answer 1

You can use a single loop with two iterators, say it1 and it2, where you increment it2 only every second iteration of the loop. Terminate when it1 has reached the end of the list. it2 will now point to the middle element of the list.