A couple weeks ago I was at an algorithm practice meetup, and our group was tasked with finding the middle node of a linked list (if the list has an even number of nodes, we were to return the second of the two middle nodes).
We worked through it together and did fairly well. The solution we came up with involved iterating through the list one and a half times, and had O(n) time complexity. We looped through the list once, updating a counter to find out how long the list was. Then we calculated which number in the list we wanted based on that length, and looped through again. We stopped and returned the node when the counter was pointing at the one we wanted.
This was pretty good, but I just knew there must be some trick to do this more easily. And indeed, when we were done, the host let us know the trick for solving it simply. It was one of those moments where once I saw the answer, it made so much sense that I was grumpy I couldn't see it before.
The answer is to use what is sometimes called the "Runner" technique. Essentially, instead of having one pointer as you loop through the linked list, you have two, and each moves at a different speed.
Imagine you have two carts moving down a track. One is moving exactly twice as fast as the other. At the moment the faster cart reaches the end, you know that by definition the slower cart must be exactly half way down the track.
That's how this works! In your loop, track two variables, say A and B. For each new node, add 1 to A and 2 to B. End the loop when B points to null (when there are no more nodes and so the list has ended), then A is pointing right where we want it! If there are an odd number, it's right in the center.
If there are an even number, it's on that second middle node.
I love little tricks like this, even as they infuriate me when I don't stumble upon them myself. Linked lists were long a confusing foe for me, but these days I'm not intimidated. I still don't like them, I think they're obtuse, but I can work with them for your average algorithm.
I look forward to continuing to learn hacks like this and to mastering more data structures.
Top comments (1)
Hello, I'm just getting into linked list myself and to be honest, its not looking great, but reading though this was super helpful in understanding the runner technique, thanks!