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:
The // should not happen condition should never happen :-) Slow should not reach the end before Fast does.
The // need to check definitely need to check if fast reaches the end. It is a common oversight that people writes
fast = fast->next->next;
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.
While loop finishes when fast reaches the end. So, we return the slow pointer.
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?
More notes:
If you analyze the reason why find_middle() produce #7/11 (#7 out of 11), you will realize that we move the slow even if fast can only move 1 node. In other words, find_middle() moves slow pointer even if fast is only one step away from the end.
In find_middle2(), we re-arrange the logic such that slow is moved ONLY when we know fast can move 2. It is just the sequence of checks and moves. The find_middle2() produces #6/11. If we break the list, the first part has 5 nodes and the second part has 6 nodes. Again, you should test with the even node case.
Discussions
Did you notice we only use head and next pointers? What does it mean?
Our test code stockDB is a doubly-linked list, anything more to learn with a forward link list?
Can you further refine the program? Got enough? How about this one?
Finding middle node of a linked list is not only an interesting question, but also a practical one. A "divide and conquer" type algorithm (like binary search or merge sort) needs to split a list into two equal size lists.