Linked Lists: Cycle Detection and Entrance Finding

Cycle Detection: Floyd's Tortoise and Hare Algorithm

To determine if a linked list contains a cycle, we use Floyd's Tortoise and Hare algorithm:

• The Slow Pointer moves 1 step at a time.
• The Fast Pointer moves 2 steps at a time.
• If there is a cycle, the fast pointer will eventually "lap" the slow pointer (the two will meet within the cycle).
• If there is no cycle, the fast pointer will reach a null termination ahead of the slow pointer.

Linked List Cycle (LeetCode 141)

boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        // If pointers meet, a cycle has been found
        if (slow == fast) return true;
    }
    return false;
}

Finding the Cycle Entrance (LeetCode 142)

Mathematical Derivation:

Let the distance from the head to the cycle entrance be a. Let the distance from the cycle entrance to the first meeting point be b. Let the remaining length of the cycle be c (total cycle length = b + c).

• Distance traveled by slow: a + b.
• Distance traveled by fast: a + b + k(b + c), where k is the number of full laps made by fast.

Since the fast pointer is twice as fast as the slow pointer: 2(a + b) = a + b + k(b + c) → a = k(b + c) - b → a = (k - 1)(b + c) + c

In the simplest case (k=1): a = c.

Conclusion: If we move one pointer from the meeting point and another pointer from the head simultaneously at the same speed (1 step at a time), they will meet at the cycle entrance!

ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    // Phase 1: Finding the meeting 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;
    
    // Phase 2: Finding the entrance
    slow = head;  // Reset slow to head
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next; // Both move at 1 step per iteration
    }
    return slow;  // Meeting point is the cycle entrance
}

Intersection of Two Linked Lists (LeetCode 160)

Using the "walk through both lists" trick to align the pointers:

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        // If pointer hits end, switch to the head of the other list
        pA = (pA == null) ? headB : pA.next;
        pB = (pB == null) ? headA : pB.next;
    }
    // Returns intersection point or null if no overlap
    return pA;
}

Principle: Let a be the unique part of A, b the unique part of B, and c the shared overlapping part.

• pA travels: a + c + b
• pB travels: b + c + a The distances are made equal, so they will arrive at the intersection point (start of c) simultaneously.

Palindrome Linked List (LeetCode 234)

Find middle -> Reverse second half -> Compare values.

boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    
    // 1. Find the middle using Fast & Slow pointers
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 2. Reverse the second half
    ListNode prev = null, cur = slow;
    while (cur != null) {
        ListNode nextTemp = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nextTemp;
    }
    
    // 3. Compare the two halves
    ListNode left = head, right = prev;
    while (right != null) {
        if (left.val != right.val) return false;
        left = left.next;
        right = right.next;
    }
    return true;
}

Summary of Fast & Slow Pointer Applications

Remove N-th Node From End of List (LeetCode 19)

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy, slow = dummy;
    // Step fast pointer ahead by n+1 so slow is at the node BEFORE the target
    for (int i = 0; i <= n; i++) fast = fast.next;
    
    while (fast != null) {
        slow = slow.next; 
        fast = fast.next; 
    }
    
    // Bridge over the node to remove it
    slow.next = slow.next.next;
    return dummy.next;
}