Problem

You are given the head of a linked list. Determine if the linked list has a cycle. If a cycle is present, find the length of the cycle. If no cycle is present, return 0.

We have already discussed the detection of linked list - here.

Examples

Example 1

1
2
3

Input:  head = [0, 1, 3, 2, 4]
output: 2
Explanation: Cycle starts at node 2

Example 2

1
2
3

Input:  head = [1, 2, 3, 4, 5, 6]
output: 4
Explanation: Cycle starts at node 3

Solution

Method 1 - Using Slow and Fast Pointer

Here are the steps:

  1. Detect Cycle: Use Floyd’s Tortoise and Hare Algorithm to detect if a cycle exists using Floyd’s Tortoise and Hare Algorithm.
  2. Find Cycle Length: If a cycle is detected, use the pointer where slow and fast pointer met to determine the length of the cycle.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class Solution {
    public int getCycleLength(ListNode head) {
        ListNode slow = head, fast = head;

        // Step 1: Detect cycle using Floyd’s Tortoise and Hare Algorithm
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) { // Cycle detected
                return findCycleLength(slow);
            }
        }

        // No cycle
        return 0;
    }

    private int findCycleLength(ListNode nodeInCycle) {
        ListNode current = nodeInCycle;
        int length = 0;

        do {
            current = current.next;
            length++;
        } while (current != nodeInCycle);

        return length;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def getCycleLength(self, head: ListNode) -> int:
        slow, fast = head, head

        # Step 1: Detect cycle using Floyd’s Tortoise and Hare Algorithm
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:  # Cycle detected
                return self.findCycleLength(slow)

        # No cycle
        return 0

    def findCycleLength(self, nodeInCycle: ListNode) -> int:
        current = nodeInCycle
        length = 0

        while True:
            current = current.next
            length += 1
            if current == nodeInCycle:
                break

        return length

Complexity

  • ⏰ Time complexity: O(n) where n is the number of nodes in the linked list
    • Cycle detection takes O(n) time, and finding cycle takes O(c) where c is cycle length, and in worst c can be n.
  • 🧺 Space complexity: O(1)