Algorithm-Day25-Linked-List-Cycle-lc-141

Posted on In , Views:

🧩 Problem Description

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

A cycle occurs when a node’s next pointer points to a previous node in the list.

Example:

1
2
Input: head = [3,2,0,-4], pos = 1 (tail connects to node index 1)
Output: true
  • Store visited nodes in a HashSet.
  • If a node is already visited → cycle detected.
1
2
3
4
5
6
7
8
9
public boolean hasCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    while (head != null) {
        if (visited.contains(head)) return true;
        visited.add(head);
        head = head.next;
    }
    return false;
}
  • Time: O(n)
  • Space: O(n)

💡 Optimal Approach: Floyd’s Tortoise and Hare

✨ Key Idea

  • Use two pointers:
    • slow moves 1 step
    • fast moves 2 steps
  • If there’s a cycle, fast will eventually “lap” slow.
  • If fast reaches null, the list has no cycle.

🔢 Java Code (Two-Pointer Approach)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head.next;

        while (slow != fast) {
            if (fast == null || fast.next == null) return false;
            slow = slow.next;
            fast = fast.next.next;
        }

        return true;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n)
  • Space Complexity: O(1)

✍️ Summary

  • This problem is a classic use case for Floyd’s Cycle Detection Algorithm.
  • Know the difference:
    • lc-141: Detect existence of a cycle
    • lc-142: Find the starting node of the cycle

Learn the two-pointer cycle detection — it’s elegant and appears in many linked list problems.