find middle

A frequently tested linked list problem is to find the middle elements of a linked list. If the list has a "size or length" member, then it is a trivial exercise of links traversal. But, what if we only have the head pointer?

I will re-use the stockDB class which has a doubly-linked list of stocks to show the process that I deal with this question.

Slow and Fast

A very smart algorithm is to use two pointers: slow and fast. Slow goes one node at a time and fast goes twice as fast. So, when fast gets to the end, the slow is right on the middle. That's what I use in the following implementation.

A few notes:

• 1. The // should not happen condition should never happen :-) Slow should not reach the end before Fast does.

  2. The // need to check definitely need to check if fast reaches the end. It is a common oversight that people writes

  3. fast = fast->next->next;

  4. The result could be mysterious because if fast is already reaching the end, fast->next is NULL. Nobody knows what the NULL is pointing to.

  5. While loop finishes when fast reaches the end. So, we return the slow pointer.

  6. What do you think? Are we good?

Here is the result:

The stockDB port1 has a stock list of 11 nodes. The result shown is at the green breakpoint. What do we get? The middle stock (CSCO) is in fact #7. Is it wrong?

Not really. If we break it into two chunk. The first part has 6 stocks and the second part has 5 stocks. That is a reasonable split. Furthermore, if you have even number of nodes (say 10), the middle will be at ??? Try it yourself.

Slow and Fast and Middle

Although it is technical ok with the find_middle implementation above, the conventional meaning of "middle" seems bugging us. How do we modify the code such that it actually reflect the middle, as in #6 out of 11?