How to find the middle node of a single linked list in a single traversal (if the length of the list is not given)

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

Following are the steps:

• Take two pointers *p1 and *p2 pointing to the head of linked list
• Start a loop and increment *p2, 2 times (with null checks)
• If *p2 is not null then increment *p1 1 time
• When *p2 reaches null; you have got the *p1 at the center

[Note: You can use iterators instead of pointer if you deal with container type linked list]

Answer 2

Say you have a std::list<T> l.

std::list<T>::iterator i = l.begin();
std::list<T>::iterator m = l.begin();
bool even = true;
while (i != list.end())
{
  if (even) ++m;
  ++i;
  even = !even;
}

Now m point to the middle of l.