Linked lists and the Runner Technique

Tortoise And Hare Sculpture On Copley Square, Boston, Massachusetts, Usa

A couple of days ago, I was going through a mock interview, and I was tasked with a question on linked list, which involved finding and returning the node where the cycle begins(if there is no cycle, return null).

For more details ->https://leetcode.com/problems/linked-list-cycle-ii/

I worked through it and found out that the easiest way to do this would be to mark each element as you visit it, but what if you’ve been told you’re not allowed to modify the list. You could keep track of the nodes you’ve encountered by putting them in a separate list. Then you would compare the current node to all the nodes in the already encountered list. If the current node ever points to a node in the already-encountered list, you have a cycle. Otherwise, you’ll get to the end of the list and see that it’s null terminated and thus acyclic.

Don’t you find a problem with this?

This would work, but in the worst case the already-encountered list would require as much memory as the original list. I just knew that there might be some easy trick/approach to do this, and in fact I was lucky enough that my interviewer hinted at using a couple of pointers. It made so much sense that I was so stupid that I couldn’t see it before. This could be have been easily solved using the Runner technique or what some may refer to as the Tortoise and Hare Algorithm or the “Floyd’s Cycle Detection Algorithm” named after its inventor Robert Floyd.

Runner Technique

The “runner” (or second pointer) technique is used in many linked list problems. The runner technique means that you iterate through the linked list with two pointers simultaneously, with one ahead of the other. The fast node might be ahead by a fixed amount, or it might be hopping multiple nodes for each one node that the slow node iterates through.

Imagine you have two cars running on a road, both of them have to cover the same distance, but one of them, say the faster car moves twice as fast as the slower one. We know that by the time the faster car reaches to the end of the linked list, the slower would be exactly at the middle of the linked list.

In the acyclic list, the faster pointer reaches the end. In the cyclic list, they both loop endlessly. The faster pointer eventually catches up with and passes the slower pointer. If the fast pointer is ever behind or equal to the slower pointer, you have a cyclic list. If it encounters a null pointer, you have an acyclic list. In outline form, this algorithm looks like this:

Pseudo code for the runner technique

Let’s start implementing the actual code:

Java Code for the above question

Let’s give a brief intro to Floyd’s Cycle-Finding Algorithm

• Traverse linked list using two pointers.
• Move one pointer(slow) by one and another pointer(fast) by two.
• If these pointers meet at the same node then there is a loop. If pointers do not meet then linked list doesn’t have a loop.
• Time complexity: O(n).
  Only one traversal of the loop is needed.
• Auxiliary Space:O(1).
  There is no space required.

The Runner Technique is amazingly helpful, for by using this technique we can solve a handful of questions on linked list, detecting loop in a linked list, finding the first node of the loop, kth to last element in the linked list, middle of the linked list ,etc being some of those.

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 am deeply grateful that someone else was around to ask these tough questions (and come up with an elegant solution) over half a century ago, before you or I even could. I look forward to continuing to learn hacks like this and to mastering more data structures.

Resources

There are a whole host of resources out there on Runner technique, if you just know what to Google for when you search for them. If you’re looking for some further reading , the links below are a good place to start.

Two Pointers Technique - GeeksforGeeks

Cycle detection in linked list with the Hare and Tortoise approach

In addition to these, the bibles of CP namely Cracking the Coding Interview by Gayle Laakmann McDowell and Programming Interviews Exposed by John Mongan, Noah Suojanen and Eric Giguere are a must.

If you like such articles, check out my hashnode profile and my blog website.

Thanks for reading.