Cracking the Coding Interview - Linked Lists - The Runner Technique
The idea behind the runner technique is simple; use two pointers that either move at different speeds or are a set distance apart and iterate through a list.
Why is this so useful? In some linked list problems you need to know the position of a certain element or the length of the list. Given that you don't always have the length of the list you are working on, the runner technique is an elegant way to solve these type of problems (and in some cases it is the only solution). Here are some examples of linked list problems where the runner technique provides an optimal solution:
- Given two lists of different lengths that merge at a point, determine the merge point
- Determine if a linked list contains a loop
- Determine if a linked list is a palindrome
- Determine the kth element of a linked list
Where do you use it? If you get handed a linked list question, and you find yourself asking these questions:
- How do I figure out where these two things meet?
- How do I figure out the midpoint?
- How do I figure out the length?
You're likely dealing with a problem where you need to use the runner technique.
How does it work? I'll illustrate one of the examples above. Given two lists of different lengths that merge at a point, determine the merge point
- Start a node at the beginning of each list on the left.
- Count how many nodes each pointer encounters. (The top list should be 5, the bottom list 4.)
- The difference between the two numbers is the difference in length of the two lists before the merge point (the difference is 1)
- Move your nodes to the beginning of each list, but the longer list should get a headstart equal to the amount of difference. (so the top list would start on its 2nd element, while the bottom list would start on its 1st).
- Move each node forward at the same speed until they meet. Where they meet is the collision point.