Detect a loop in LL
MediumFloyd: a fast pointer laps a slow one
Problem
Given the head of a singly linked list. Return true if a loop exists in the linked list or return false. A loop exists in a linked list if some node in the list can be reached again by continuously following the next pointer. Internally, pos is used to denote the index(0-based) of the node from where the loop starts. Note that pos is not passed as a parameter.
Run slow and fast pointers; if they ever meet, the list has a loop (Floyd's tortoise and hare).
The idea
Move one pointer one step and another two steps. If there is a cycle the fast pointer eventually laps the slow one and they meet; if there is not, the fast pointer reaches null. It needs no extra memory, unlike a visited set.
The trick
- They must meet inside a cycle — the gap closes by one each step.
- Check `fast && fast.next` before advancing, or you will dereference null.
- O(n) time, O(1) space.
Step 1 of 5. Slow moves one step, fast moves two. In a loop the fast pointer eventually laps the slow one.
They meet iff a cycle exists.
1let slow = head, fast = head;2while (fast && fast.next) {3 slow = slow.next;4 fast = fast.next.next;5 if (slow === fast) return true;6}7return false;Input
- list
- [3, 2, 0, -4]
Memory
- slow
- = 0
- fast
- = 0
Output
- cycle
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- list = 1 -> 2 -> 3 -> 4 -> (back to 2)
- Output:
- true
- Explanation:
- The tail loops back, so a cycle exists.
Example 2
- Input:
- list = 1 -> 2 -> 3
- Output:
- false
- Explanation:
- It ends normally with no loop.
Example 3
- Input:
- list = 1 -> (back to 1)
- Output:
- true
- Explanation:
- A node pointing to itself is a cycle.
Constraints
- 0 <= number of nodes in the cycle <= 10^5
- 0 <= ListNode.val <= 10^4
- pos is -1 or a valid index in the linked list
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.