Fast and slow pointers coding pattern

The fast and slow pointers pattern, also known as the "hare and tortoise" algorithm, is a popular technique used to solve various coding problems. In this pattern, two pointers are used to traverse a data structure, typically a linked list or an array, at different speeds. Here are three examples of how to use the fast and slow pointers pattern in JavaScript:

Example 1: Linked List Cycle

Given a linked list, determine whether it has a cycle or not.

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true;
    }
  }

  return false;
}

// Example usage
const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2;

console.log(hasCycle(node1)); // true

In this example, we use two pointers, slow and fast, to traverse the linked list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If the linked list has a cycle, the fast pointer will eventually catch up to the slow pointer, and we can return true. Otherwise, we return false.

Example 2: Middle of the Linked List

Given a linked list, find the middle node.

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

function middleNode(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow;
}

// Example usage
const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);
const node5 = new ListNode(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

console.log(middleNode(node1)); // ListNode { val: 3, next: ListNode { val: 4, next: ListNode { val: 5, next: null } } }

In this example, we again use two pointers, slow and fast, to traverse the linked list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the linked list, the slow pointer will be at the middle node, which we can return.

Example 3: Nth Node from the End of a Linked List

Given a linked list, find the nth node from the end of the list.

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

function nthFromEnd(head, n) {
  let slow = head;
  let fast = head;

  for (let i = 0; i < n; i++) {
    fast = fast.next;
  }

  while (fast) {
    slow = slow.next;
    fast = fast.next;
  }

  return slow;

In the third example, we want to find the nth node from the end of a linked list. To do this, we again use two pointers, slow and fast, to traverse the linked list. However, this time we need to start the fast pointer n nodes ahead of the slow pointer.

So, we first move the fast pointer n nodes ahead of the slow pointer by iterating over the list n times. Once the fast pointer is n nodes ahead, we move both pointers forward one node at a time until the fast pointer reaches the end of the linked list. At this point, the slow pointer will be pointing to the nth node from the end of the list, which we can return.

This approach has a time complexity of O(n) because we iterate over the linked list twice, with a gap of n nodes between the two pointers.