Linked List Cycle

Share

Given the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node in the list can be reached again by continuously following the next pointer. Return true if a cycle exists, otherwise return false.

Example 1
Input: head = [3, 2, 0, -4], pos = 1 (tail connects to node at index 1)
Output: true
Explanation: There is a cycle; the tail connects back to node with value 2.
Example 2
Input: head = [1, 2], pos = 0
Output: true
Explanation: The tail connects back to the head.
Example 3
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the list.

Solution Approach - Floyd's Tortoise and Hare

Floyd's cycle detection algorithm uses two pointers moving at different speeds. If a cycle exists, the fast pointer will eventually lap the slow pointer and they will meet inside the cycle. If no cycle exists, the fast pointer reaches the end of the list.

  • Initialize two pointers: slow and fast, both starting at head.
  • In each iteration, move slow one step forward and fast two steps forward.
  • If fast or fast.next becomes null, the list has no cycle: return false.
  • If slow == fast, the two pointers have met inside a cycle: return true.
Java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class LinkedListCycle {

    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;       // move 1 step
            fast = fast.next.next;  // move 2 steps
            if (slow == fast) {
                return true; // cycle detected
            }
        }
        return false; // fast reached end, no cycle
    }
}
Complexity Analysis:

Time complexity: O(n) where n is the number of nodes. In the worst case (no cycle), fast pointer traverses all nodes. With a cycle, the two pointers meet after at most n iterations.
Space complexity: O(1) as only two pointers are used regardless of list size.