The Runner Technique in JavaScript

A Two-Pointer Strategy for Linked Lists: Mastering Linked Lists

While linked lists aren’t native to JavaScript like arrays, they’re an essential data structure in algorithmic problems and challenges. Often, developers find themselves implementing linked lists from scratch in JavaScript and encounter classic problems that require specific strategies. Enter the “runner” or “two-pointer” technique, an elegant approach to traverse linked lists efficiently.

Two Runners, on your linked list

What is the Runner Technique?

Imagine two athletes on a track, one sprinting and the other jogging. The runner technique is much like this analogy. It employs two pointers that navigate through the linked list, but at different speeds. The genius behind this method is in the relative movement of these pointers.

Applications of the Runner Technique

Here are some noteworthy uses of the runner technique in the context of linked lists:

Detecting Cycles: Cycles in a linked list can lead to infinite loops during traversal. To detect them, the runner technique proposes two pointers: one moving at twice the speed of the other. If a cycle exists, the faster pointer (or “runner”) will eventually catch up with the slower one.

Finding the Middle of a Linked List: Identifying the center of a linked list without knowing its length beforehand can be tricky. Using the runner technique, as the faster pointer advances two steps, the slower one takes one. By the time the fast pointer reaches the end, the slow pointer will be at the middle.

Locating the n-th Node from the End: To find a specific node counting from the end, advance the fast runner n nodes ahead first. Then start both pointers. When the fast pointer reaches the end, the slow one is at the desired position.

Example in Modern JavaScript

To understand the runner technique’s application, let’s delve into a simple linked list cycle detection in JavaScript:

The same code with comments:

// Class representing a single node in a linked list
class ListNode {
  // Constructor for the ListNode class
  constructor(value) {
    // Set the value of the node to the provided value
    this.value = value;   
    // Initialize the 'next' pointer to null (indicating no subsequent node by default)
    this.next = null;    
  }
}

// Function to check if a given linked list (starting from 'head') contains a cycle
function hasCycle(head) {
  // If the list is empty (head is undefined or null) or contains only a single node (head's next is null or undefined),
  // return false as a cycle cannot exist in such cases
  if (!head || !head.next) return false;

  // Initialize two pointers: 'slow' and 'fast', both pointing to the head of the list initially
  let slow = head;
  let fast = head;

  // Traverse the list until either the fast pointer reaches the end or the node just before the end
  while (fast && fast.next) {
    // Move the slow pointer one node at a time
    slow = slow.next;
    // Move the fast pointer two nodes at a time
    fast = fast.next.next; 

    // If the slow and fast pointers meet (point to the same node), then a cycle exists in the list
    if (slow === fast) return true;
  }

  // If the loop completes without the pointers meeting, then the list doesn't have a cycle
  return false;
}

In the code above, the ListNode class represents our linked list's nodes. The hasCycle function uses the runner technique, with a slow and a fast pointer, to identify potential cycles.

Advantages of the Runner Technique

Why should one adopt the runner technique in their JavaScript endeavors?

Efficiency: It frequently allows problems to be solved in one pass, optimizing time complexity.

Memory Usage: The runner technique often requires O(1) space, making it memory-efficient.

Simplicity: Even with its advantages, the underlying logic remains easy to understand and implement, aiding debugging and readability.

Conclusion

Whether you’re working with JavaScript or any other programming language, understanding the nuances of data structures like linked lists is vital. The runner technique provides a powerful tool for anyone dealing with such structures in JavaScript. By leveraging its simplicity and efficiency, you can solve classic problems and ensure optimal performance in your applications. So, the next time a linked list problem arises, remember the two-pointer strategy and give the “runner” a go!