Algorithm Patterns: Fast & Slow pointer

The Fast and Slow pointer approach, also known as Hare & Tortoise strategy, is a two-pointers algorithm that traverses the array (or sequence/LinkedList) at various speeds. When working with cyclic LinkedLists or arrays.

Example: LinkedList Cycle

Given the head of a Singly LinkedList, write a function to determine if the LinkedList has a cycle in it or not.

Consider two-pointers slow and fast traversing the LinkedList. The slow pointer moves one step and the fast pointer moves two steps in each iteration. This leads us to two conclusions:

• If the linked list doesn’t have a cycle in it. The fast pointer will reach the end before the slow.
• If the linked list has a cycle. The two-pointers will keep moving in the cycle infinitely. However, at some point, both of these pointers will collide.

Java Code

class ListNode {
  int value = 0;
  ListNode next;

  ListNode(int value) {
    this.value = value;
  }
}

class LinkedListCycle {

  public static boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
      fast = fast.next.next;
      slow = slow.next;
      if (slow == fast)
        return true; // found the cycle
    }
    return false;
  }
}

Time Complexity

The time complexity of the above algorithm is O(N), where ’N’ is the total number of elements in the given array.

Space Complexity

The Space complexity of this algorithm is O(1). Because we didn’t use any extra memory.

Fast & Slow Pointers — LeetCode Problems

• Linked List Cycle (easy)
• Happy Number (easy)
• Middle of the Linked List (easy)
• Palindrome Linked List (easy)
• Linked List Cycle II (medium)
• Find the Duplicate Number (medium)
• Convert Sorted List to Binary Search Tree (medium)
• Rotate List (medium)
• Odd Even Linked List (medium)
• Reorder List (medium)
• Circular Array Loop (medium)

The more you practice the better you get.