Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Approach: Floyd’s Tortoise and Hare (Optimal Solution)

Algorithm

1. Use two pointers: a slow tortoise moving one step and a fast hare moving two steps
2. Start both at head
3. While hare and hare.next are not null, advance both pointers
4. If the two pointers ever meet, a cycle exists
5. If hare reaches the end, there is no cycle

Key Insight

If a cycle exists, the fast pointer will eventually lap the slow pointer inside the cycle, causing them to meet. If there is no cycle, the fast pointer reaches the end of the list first. This avoids any extra memory.

Time & Space Complexity

• Time Complexity: O(n) - linear in the number of nodes
• Space Complexity: O(1) - only constant extra space used

Java Implementation

public class LinkedListCycle {

    /**
     * Definition for singly-linked list.
     */
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    /**
     * Determine whether a linked list has a cycle.
     * @param head Head of the linked list
     * @return true if the list has a cycle, false otherwise
     */
    public static boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;       // move one step
            fast = fast.next.next;  // move two steps

            // If they meet, a cycle exists
            if (slow == fast) {
                return true;
            }
        }

        return false;
    }

    // Helper method to build a list with an optional cycle
    public static ListNode buildList(int[] values, int pos) {
        ListNode head = null;
        ListNode tail = null;
        ListNode cycleNode = null;

        for (int i = 0; i < values.length; i++) {
            ListNode node = new ListNode(values[i]);
            if (head == null) {
                head = node;
            } else {
                tail.next = node;
            }
            tail = node;
            if (i == pos) {
                cycleNode = node;
            }
        }

        // Create the cycle
        if (cycleNode != null && tail != null) {
            tail.next = cycleNode;
        }

        return head;
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        ListNode head1 = buildList(new int[]{3, 2, 0, -4}, 1);
        System.out.println("Input: head = [3,2,0,-4], pos = 1");
        System.out.println("Output: " + hasCycle(head1)); // Expected: true

        // Test case 2
        ListNode head2 = buildList(new int[]{1, 2}, 0);
        System.out.println("Input: head = [1,2], pos = 0");
        System.out.println("Output: " + hasCycle(head2)); // Expected: true

        // Test case 3
        ListNode head3 = buildList(new int[]{1}, -1);
        System.out.println("Input: head = [1], pos = -1");
        System.out.println("Output: " + hasCycle(head3)); // Expected: false
    }
}

Example Walkthrough

For head = [3,2,0,-4] with a cycle back to node 1:

1. slow=3, fast=3
2. slow=2, fast=0
3. slow=0, fast=2
4. slow=-4, fast=-4. They meet. Return true

For head = [1] with no cycle:

1. slow=1, fast=1
2. fast.next is null, loop ends. Return false

Alternative Hash Set Approach

import java.util.HashSet;
import java.util.Set;

public static boolean hasCycleWithSet(ListNode head) {
    Set<ListNode> seen = new HashSet<>();
    ListNode curr = head;

    while (curr != null) {
        // If we've seen this node before, there's a cycle
        if (seen.contains(curr)) {
            return true;
        }
        seen.add(curr);
        curr = curr.next;
    }

    return false;
}

The hash set approach stores visited nodes in O(n) memory, which does not satisfy the follow-up’s constant memory requirement.

Key Insights

1. Two Pointers: The tortoise and hare detect cycles in constant space
2. Meeting Proof: If a cycle exists, the hare necessarily catches the tortoise inside it
3. Null Checks: Guard against null pointers when advancing the fast pointer
4. Follow-up Solved: Uses only O(1) memory as requested

Floyd’s cycle detection algorithm is the optimal solution, providing linear time complexity with constant space.