Cracking the Coding Interview – Linked Lists – The Runner Technique

I’ve been going over the Linked List section of Cracking the Coding Interview and I’m realizing that almost every time I get stumped with a problem the solution is the Runner Technique (or slow/fast pointers).

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 many linked list problems you need to know the position of a certain element or the overall 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’s the only solution). Here are some examples of linked list problems where the runner technique provides an optimal solution:

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 most 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 pointTerrible Branched Linked List Picture

  1. Start a node at the beginning of each list on the left.
  2. Count how many nodes each pointer encounters. (The top list should be 5, the bottom list 4.)
  3. The difference between the two numbers is the difference in length of the two lists before the merge point (the difference is 1)
  4. 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).
  5. Move each node forward at the same speed until they meet. Where they meet is the collision point.

Each of the links above contains code and solutions to each of the problems. I hope this example and the ones above show the usefulness of this approach.

There are also some examples located here of various linked list algorithms problems and solutions written in JavaScript.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s