Lists and Cycles => O(n)

A classic problem is to detect if there are cycles in a list. This problem can be solved by using the 2-pointer technique. Imagine two runners. If they are running on a circular path, a faster runner will reach the slower one (see the tortoise and hare math).

To detect the node that starts the cycle, first you use the 2PT to detect if there is a cycle, then reset the slow pointer and advance both 1 step at a time until they meet again.

2PT In Linked List Template

ListNode slow = head;
ListNode fast  head;

// change condition to fit problem
while (slow != null && fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) { // fit to problem
        return true;
    }
}
return false; // fit to problem

Tips:

• O(n+m) = O(n) where m<n is the number of steps to catch up before the two pointers meet if there are cycles.

Example: Reverse Array

2PT II

You can also use two pointers that move at different speed.

Example: Remove el from array in place, return new len