How do you find the middle node of a linked list, and what are the two approaches?
There are two approaches. The first one counts the nodes first and then walks to the middle. The second one uses two pointers that move at different speeds and never counts anything.
So how do you find the middle node? The middle of a list with an odd number of nodes is the one in the middle. The middle of a list with an even number of nodes has no single answer, and the usual rule is to take the second of the two middle nodes.
the list the nodes the middle
----------- --------- ---------------
1 -> 2 -> 3 3 2
1 -> 2 -> 3 -> 4 4 3
And here is how the two approaches compare.
the approach the time the space the number of passes
----------------- --------- ---------- -------------------
count then walk O(n) O(1) two
fast and slow O(n) O(1) one
So the counting version is simpler to understand. You walk the list and count the nodes. Then you walk again and stop after half of the count. The fast and slow version is more clever and it is the one to write in an interview, because it only goes through the list once.
And there is a third way that is worth knowing about. You can keep a running count as you go and remember the node that was in the middle, but that needs a count and it is not simpler than the first way.
And why do interviewers like this question? Because there is no clever trick to hide behind. The list can only be walked in one direction, so the only thing you can do is count or use two pointers. And the answer is the same either way, so the interviewer sees how you write and explain the code.
So the rule to remember is this. Count and walk, or use two pointers, and both of them take O of n for the time.
The next two questions in this topic show the code for both approaches.