cycle linked list
cycle detection
algorithms
programming
data structures

How does finding a cycle start node in a cycle linked list work?

Data Structures & Algorithms practice on Codemia

Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.

Practice algorithms

Introduction

In the context of data structures, a linked list is a series of nodes where each node contains data and a pointer to the next node in the sequence. A common problem with linked lists is detecting cycles, which occur when a node's next reference points back to a previous node in the list, creating a loop. Identifying the start of this cycle can help prevent errors in computations and data manipulations involving linked lists.

This article explores how to detect the starting node of a cycle in a linked list, using Floyd's Tortoise and Hare algorithm. This approach is efficient, operating in O(n) time complexity with O(1) space complexity.

Floyd's Tortoise and Hare Algorithm

Concept

Floyd's Tortoise and Hare algorithm is a two-pointer approach that involves two markers moving through the linked list at different speeds. Here's how it works:

  1. Two Pointers: We use two pointers, slow (tortoise) and fast (hare).
  2. Movement: slow moves one step at a time, while fast moves two steps.
  3. Detection of Cycle: If there is a cycle, fast and slow will eventually meet within the cycle.
  4. Finding Cycle Start: Once a meeting point is identified, keep one pointer at the meeting position and reset the other pointer to the start of the linked list. Move both pointers one step at a time. The point at which they meet again is the start of the cycle.

Technical Explanation

  1. Initialization:
    • Begin with slow and fast pointers both pointing to the head of the linked list.
  2. Cycle Detection:
    • Iterate through the list, moving the pointers with their respective speeds (slow by one and fast by two).
    • If fast becomes null or fast.next becomes null, the list has no cycle.
    • If slow equals fast, a cycle exists.
  3. Locating Cycle Start:
    • Reset slow to the head of the list, keeping fast at the meeting point.
    • Move both pointers at the same speed (one step at a time).
    • The point where they meet again is the start of the cycle.

Code Example

Here is a Python implementation:

python
1class ListNode:
2    def __init__(self, value=0, next=None):
3        self.value = value
4        self.next = next
5
6def findCycleStart(head):
7    slow = head
8    fast = head
9
10    # Detect cycle
11    while fast and fast.next:
12        slow = slow.next
13        fast = fast.next.next
14        if slow == fast:
15            break
16    else:
17        return None  # No cycle
18
19    # Find cycle start
20    slow = head
21    while slow != fast:
22        slow = slow.next
23        fast = fast.next
24
25    return slow

Example

Consider the following linked list example:

  • One element (2) links back to another element (1), forming a cycle:
 
1 -> 2 -> 3
      ^    |
      |____|

By applying the algorithm, the cycle is detected, and the start node (node with value 2) is identified.

Summary Table

StepDescriptionDetails
InitializationStart slow and fast at headPointers: slow, fast
Cycle DetectionMove slow by one, fast by twoDetect meeting point
Cycle VerificationIf fast or fast.next is null, no cycleCycle doesn't exist
Locate Cycle StartReset one pointer to head, keep one at meeting point Advance both by oneMeeting point is start

Conclusion

Floyd's Tortoise and Hare algorithm is a clever technique for detecting cycles in linked lists. By effectively managing pointers and leveraging the inherent properties of cycles, it offers a straightforward yet powerful solution. Understanding this approach is crucial for tackling problems involving cycle detection in linked data structures.


Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Data Structures & Algorithms practice on Codemia

Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.

Practice algorithms