Length of loop in LL
MediumWalk one lap from the meeting point
Problem
Given the head of a singly linked list, find the length of the loop in the linked list if it exists. Return the length of the loop if it exists; otherwise, return 0. 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.
Find the meeting point with slow/fast pointers, then count steps to walk the loop once.
The idea
Once the two pointers meet you are guaranteed to be inside the cycle, so keep one still and walk the other until it comes back, counting steps. That count is the cycle's length.
The trick
- Any node inside the cycle works as the starting point for the lap.
- Return 0 when the fast pointer reaches null — there is no cycle.
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 -> 5, tail links to index 1
- Output:
- 4
- Explanation:
- Nodes 2,3,4,5 form a loop of length 4.
Example 2
- Input:
- list = 1 -> 2 -> 3, no loop
- Output:
- 0
- Explanation:
- No cycle → 0.
Example 3
- Input:
- list = 1 -> 2, tail links to index 0
- Output:
- 2
- Explanation:
- Both nodes loop → length 2.
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:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.