Linked List Cycle

141.Linked List Cycle

Linked List

Two Pointers

Problem Statement:

Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if any node in the list can be reached again by continuously following the next pointer.

Example:

Input:

head = [3,2,0,-4] pos = 1

→

Output:

true

The -4 node's next pointer connects back to node at index 1 (0-based), forming a cycle.

Algorithm:

1. Use two pointers: slow (moves one step) and fast (moves two steps)
2. If there's a cycle, fast pointer will eventually meet slow pointer
3. If fast reaches null, there is no cycle
4. Return true if pointers meet, false otherwise

public boolean hasCycle(ListNode head) {
    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 (slow == fast) return true;  // Cycle detected
    }

    return false;  // No cycle if fast reaches end
}

Complexity:

Time: O(n) | Space: O(1)