Linked List Two Pointers (Fast & Slow, Middle, Cycle)

Core Concept of Fast & Slow Pointers

• Fast Pointer: Moves 2 steps forward at a time.
• Slow Pointer: Moves 1 step forward at a time.
• If a Cycle Exists: The pointers will eventually collide within the cycle.
• If No Cycle Exists: The fast pointer will reach a null termination ahead of the slow pointer.

Middle of the Linked List (LeetCode 876)

ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;  // Returns the second middle node for even-length lists
}

Linked List Cycle I (LeetCode 141)

Check if a cycle exists:

boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

Linked List Cycle II (LeetCode 142)

Find the entrance node of the cycle (Floyd's Cycle-Finding Algorithm):

ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    // 1. Find the collision point
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    
    // No cycle detected
    if (fast == null || fast.next == null) return null; 

    // 2. Move one pointer to the head, keep the other at the collision point.
    // Move both at the same speed; the next collision is the entrance.
    fast = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

Mathematical Proof:

• Let distance from head to entrance = a.
• Let distance from entrance to collision = b.
• Let distance from collision back to entrance = c.
• Slow travels a + b; Fast travels a + b + c + b (assuming 1 lap).
• Fast's speed is 2x: a + 2b + c = 2(a + b) → c = a.
• Thus, moving from head and collision simultaneously at the same speed (1 step) will lead to a meeting at the entrance after exactly a steps.

Intersection of Two Linked Lists (LeetCode 160)

Find the starting node where two lists intersect:

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = (pA == null) ? headB : pA.next; // Switch head after reaching the end
        pB = (pB == null) ? headA : pB.next;
    }
    return pA;
}

Principle: Both pointers combined will travel exactly lenA + lenB steps before meeting at the intersection (or both reaching null).

Sort List (LeetCode 148)

Sort a linked list in O(n log n) time and O(1) space (recursive stack excluded) using Bottom-up Merge Sort:

ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    
    // Find middle and split the list
    ListNode mid = getMid(head);
    ListNode rightHead = mid.next;
    mid.next = null;
    
    // Recursive sort
    ListNode left = sortList(head);
    ListNode right = sortList(rightHead);
    return mergeTwoLists(left, right);
}

private ListNode getMid(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow; // Returns the tail of the first half
}

Reorder List (LeetCode 143)

Target: $L_0 \rightarrow L_1 \rightarrow \dots \rightarrow L_{n-1} \rightarrow L_n$ transforms into $L_0 \rightarrow L_n \rightarrow L_1 \rightarrow L_{n-1} \rightarrow L_2 \rightarrow L_{n-2} \dots$

Steps:

1. Find the Middle: Using Fast & Slow pointers.
2. Reverse Second Half: From the middle onwards.
3. Zig-Zag Merge: Combine the first and reversed second half.

void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    
    // 1. Find the split point
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next; 
        fast = fast.next.next;
    }
    
    // 2. Reverse the second half
    ListNode second = reverseList(slow.next);
    slow.next = null; // Split the lists
    
    // 3. Zig-zag merge
    ListNode first = head;
    while (second != null) {
        ListNode nextFirst = first.next;
        ListNode nextSecond = second.next;
        
        first.next = second;
        second.next = nextFirst;
        
        first = nextFirst;
        second = nextSecond;
    }
}