Data Structures & AlgorithmsCircular Linked Lists

Circular Linked Lists

LevelIntermediate

Duration55 mins

TopicCircular Linked Lists

4 / 4

Detecting the End Condition

The Infinite Loop Trap

In linear linked lists, termination is trivial: follow next pointers until you hit null. The language of the code is simple:

while (current !== null) {
    // process current
    current = current.next;
}

But in a circular linked list, there is no null. Every node has a valid successor. The last node's next points back to the first. If you write the simple while loop above, you don't get termination—you get an infinite loop.

This is the defining challenge of working with circular structures: How do we know when to stop?

The answer isn't complex, but getting it wrong leads to programs that hang forever. Understanding the various techniques for detecting the 'end' (or more accurately, detecting a complete cycle) is essential for writing correct circular linked list code.

What You Will Master

By the end of this page, you will understand multiple techniques for detecting when you've completed a full cycle in a circular linked list. You'll know when to use each technique, their trade-offs, and how to avoid the infinite loop trap. This knowledge is critical for writing bug-free circular linked list code.

The Fundamental Challenge

Let's deeply understand why the termination problem exists and what makes it different from linear lists.

Linear List Termination:

head → [A] → [B] → [C] → [D] → null

The structure itself contains the termination signal: null. No matter where you start, if you follow next pointers, you will eventually reach null. You don't need to know how many nodes exist or remember where you started.

Circular List Non-Termination:

head → [A] → [B] → [C] → [D] ─┐
        ↑                      │
        └──────────────────────┘

Following next pointers from any node will never encounter null. You'll visit A, B, C, D, A, B, C, D, A... indefinitely. The structure is continuous; there is no built-in termination signal.

The Core Question:

Since the structure doesn't tell us when to stop, we must introduce external knowledge or markers to detect cycle completion. The techniques fall into several categories:

Termination Detection Approaches

•Entry Point Comparison — Remember where you started; stop when you return to it
•Count-Based Termination — Know how many elements exist; stop after visiting that many
•Marker-Based Detection — Use a special value or flag to indicate the starting point
•Visited Tracking — Maintain a set of visited nodes; stop when you revisit one
•Two-Pointer Techniques — Use the fast/slow pointer approach to detect cycles

The Classic Bug

The most common bug when transitioning from linear to circular lists is copying the 'while (current !== null)' pattern. This will compile fine, but your program will never terminate. Always verify your termination condition when working with circular structures.

Entry Point Comparison (Do-While Pattern)

The most common and idiomatic approach is entry point comparison: remember the starting node, traverse the list, and stop when you return to that starting node.

The Do-While Pattern:

In languages with do-while loops, the pattern is elegant:

do {
    // Process current
    current = current.next;
} while (current !== startNode);

We use do-while (not while) because we need to visit the starting node at least once before checking if we've returned to it. A while loop with the same condition would immediately terminate without processing any nodes.

Entry Point Comparison Traversal
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// Technique 1: Do-While with Entry Point Comparison
function traverseWithDoWhile<T>(head: CircularNode<T> | null): T[] {
    if (head === null) {
        return [];
    }
    
    const result: T[] = [];
    let current = head;
    
    // Do-while: visit node before checking termination
    do {
        result.push(current.data);
        current = current.next;
    } while (current !== head);  // Stop when we return to start
    
    return result;
}
 
// Why do-while and not while?
// Consider this buggy version:
function buggyTraversal<T>(head: CircularNode<T> | null): T[] {
    if (head === null) {
        return [];
    }
    
    const result: T[] = [];
    let current = head;
    
    // BUG: This checks BEFORE processing the first node
    while (current !== head) {  // Immediately false! current IS head
        result.push(current.data);
        current = current.next;
    }
    
    // This returns [] even for a non-empty list!
    return result;
}
 
// Alternative: Use a flag for languages without do-while
function traverseWithFlag<T>(head: CircularNode<T> | null): T[] {
    if (head === null) {
        return [];
    }
    
    const result: T[] = [];
    let current: CircularNode<T> | null = head;
    let isFirst = true;
    
    while (isFirst || current !== head) {
        isFirst = false;
        result.push(current!.data);
        current = current!.next;
    }
    
    return result;
}

When to Use This Technique

Entry point comparison is best when: (1) you have a known starting point, (2) you need to visit every node exactly once, and (3) you don't have a size counter. It's the most common general-purpose traversal pattern for circular lists.

Count-Based Termination

If you maintain a size counter in your circular linked list implementation, you can use count-based termination: visit exactly size nodes and then stop.

Advantages over Entry Point Comparison:

No reference comparison — Some node types might not support equality checks efficiently
Works for partial traversals — Easy to visit only the first N elements
Loop counting — Easy to determine how many cycles you've completed

Disadvantages:

Requires accurate size — If size is wrong, behavior is wrong
Maintenance overhead — Must update size on every insert/delete

Count-Based Termination
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Technique 2: Count-Based Termination
class CircularListWithSize<T> {
    head: CircularNode<T> | null = null;
    size: number = 0;
    
    // Traverse exactly 'size' elements
    traverse(): T[] {
        if (this.head === null || this.size === 0) {
            return [];
        }
        
        const result: T[] = [];
        let current = this.head;
        
        for (let i = 0; i < this.size; i++) {
            result.push(current.data);
            current = current.next;
        }
        
        return result;
    }
    
    // Visit first N elements (with wraparound if N > size)
    visitN(n: number): T[] {
        if (this.head === null || this.size === 0) {
            return [];
        }
        
        const result: T[] = [];
        let current = this.head;
        
        for (let i = 0; i < n; i++) {
            result.push(current.data);
            current = current.next;
        }
        
        return result;
    }
    
    // Complete K full cycles
    traverseKCycles(k: number): T[] {
        if (this.head === null || this.size === 0) {
            return [];
        }
        
        const totalVisits = this.size * k;
        const result: T[] = [];
        let current = this.head;
        
        for (let i = 0; i < totalVisits; i++) {
            result.push(current.data);
            current = current.next;
        }
        
        return result;
    }
    
    // Find element at logical index (with wraparound)
    getAt(index: number): T | null {
        if (this.head === null || this.size === 0) {
            return null;
        }
        
        // Handle negative indices and indices > size with modulo
        const normalizedIndex = ((index % this.size) + this.size) % this.size;
        
        let current = this.head;
        for (let i = 0; i < normalizedIndex; i++) {
            current = current.next;
        }
        
        return current.data;
    }
}
 
// Example: Demonstrate count-based access
const list = new CircularListWithSize<string>();
// Assume list has: A → B → C → D → (back to A), size = 4
 
// list.getAt(0)  → A
// list.getAt(3)  → D
// list.getAt(4)  → A (wraps around)
// list.getAt(10) → C (wraps: 10 % 4 = 2)
// list.getAt(-1) → D (wraps: (-1 % 4 + 4) % 4 = 3)

Modular Arithmetic and Circular Access

Count-based access naturally enables modular arithmetic for indices. index % size gives you the effective position in the cycle. This is powerful for applications where 'wrapping around' is semantically meaningful, like clock arithmetic or rotating schedules.

Sentinel or Marker-Based Detection

Another approach is to use a sentinel marker to identify the 'start' of the list. This can be:

A dedicated sentinel node — A special node that doesn't hold real data
A marked data value — A reserved value that signals 'this is the start'
A modification to the starting node — Temporarily mark it during traversal

Sentinel Node Approach:

With a sentinel node, the list has one node that's always identifiable as the entry/exit point. The 'real' head is sentinel.next, and the 'real' tail is sentinel.prev (in doubly circular lists).

When traversing, you start at sentinel.next and stop when you reach sentinel again, rather than comparing to your starting point.

Sentinel-Based Traversal
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// Technique 3: Sentinel Node for End Detection
class CircularListWithSentinel<T> {
    private sentinel: CircularNode<T>;
    
    constructor() {
        // Sentinel with a recognizable marker (null data in this case)
        this.sentinel = {
            data: null as unknown as T,
            next: null as unknown as CircularNode<T>,
        };
        // Sentinel points to itself in an empty list
        this.sentinel.next = this.sentinel;
    }
    
    isEmpty(): boolean {
        return this.sentinel.next === this.sentinel;
    }
    
    insertAfterSentinel(data: T): void {
        const newNode: CircularNode<T> = {
            data,
            next: this.sentinel.next,
        };
        this.sentinel.next = newNode;
    }
    
    // Traverse using sentinel as the stopping point
    traverse(): T[] {
        const result: T[] = [];
        let current = this.sentinel.next;
        
        // Stop when we reach the sentinel
        while (current !== this.sentinel) {
            result.push(current.data);
            current = current.next;
        }
        
        return result;
    }
    
    // Search for a value
    find(value: T): CircularNode<T> | null {
        let current = this.sentinel.next;
        
        while (current !== this.sentinel) {
            if (current.data === value) {
                return current;
            }
            current = current.next;
        }
        
        return null; // Not found
    }
}
 
// Note: With a sentinel, we CAN use while loop!
// The sentinel acts like null in linear lists—it terminates traversal.

The Sentinel Advantage

With a sentinel node, you can use the familiar 'while (current !== sentinel)' pattern—similar to 'while (current !== null)' in linear lists. The sentinel provides a consistent stopping point that works even when the list is empty.

Visited Tracking with External Memory

When you don't have a known starting point or when detecting cycles in an unknown structure, you may need to track which nodes you've visited using external memory (a hash set, for example).

Use Cases:

Cycle detection in unknown lists — You receive a list and don't know if it's circular
Multiple traversals from different starting points — Need to avoid revisiting
Graph-like structures — Nodes might be reachable from multiple paths

Trade-off:

This approach uses O(n) additional space but provides O(1) lookup per node. It's overkill for simple circular list traversal but essential for more complex scenarios.

Visited Tracking
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Technique 4: Visited Set Tracking
function traverseWithVisitedSet<T>(startNode: CircularNode<T> | null): T[] {
    if (startNode === null) {
        return [];
    }
    
    const result: T[] = [];
    const visited = new Set<CircularNode<T>>();
    let current: CircularNode<T> | null = startNode;
    
    while (current !== null && !visited.has(current)) {
        visited.add(current);
        result.push(current.data);
        current = current.next;
    }
    
    return result;
}
 
// More useful: Cycle detection in an unknown list
interface Node<T> {
    data: T;
    next: Node<T> | null;
}
 
function detectCycleWithSet<T>(head: Node<T> | null): {
    hasCycle: boolean;
    cycleStart: Node<T> | null;
} {
    if (head === null) {
        return { hasCycle: false, cycleStart: null };
    }
    
    const visited = new Set<Node<T>>();
    let current: Node<T> | null = head;
    
    while (current !== null) {
        if (visited.has(current)) {
            // We've seen this node before—cycle detected!
            return { hasCycle: true, cycleStart: current };
        }
        visited.add(current);
        current = current.next;
    }
    
    // Reached null—no cycle
    return { hasCycle: false, cycleStart: null };
}
 
// Complexity Analysis:
// Time: O(n) — each node visited once
// Space: O(n) — storing all visited nodes

Memory Overhead

Visited tracking requires O(n) additional space. For very large lists or memory-constrained environments, this may be prohibitive. Floyd's cycle detection (next section) provides O(1) space cycle detection, though with different capabilities.

Floyd's Cycle Detection (Tortoise and Hare)

Floyd's cycle detection algorithm, also known as the tortoise and hare algorithm, is an elegant O(1) space technique for detecting cycles in linked structures. It uses two pointers moving at different speeds.

The Algorithm:

Initialize two pointers at the head: slow (tortoise) and fast (hare)
Move slow one step at a time, fast two steps at a time
If there's no cycle, fast will reach null
If there's a cycle, fast will eventually catch up to slow inside the cycle

Why It Works:

Imagine two runners on a circular track. If one runs twice as fast, they will inevitably lap the slower runner. The same logic applies: if there's a cycle, the fast pointer will eventually 'lap' the slow pointer, and they'll meet.

Mathematical Insight:

Once both pointers are in the cycle, the distance between them decreases by 1 with each step (fast gains 2 - 1 = 1 position per iteration). Therefore, they must meet within the length of the cycle.

Floyd's Cycle Detection
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// Floyd's Cycle Detection Algorithm
interface LinkedNode<T> {
    data: T;
    next: LinkedNode<T> | null;
}
 
function detectCycleFloyd<T>(head: LinkedNode<T> | null): boolean {
    if (head === null || head.next === null) {
        return false;
    }
    
    let slow: LinkedNode<T> | null = head;
    let fast: LinkedNode<T> | null = head;
    
    while (fast !== null && fast.next !== null) {
        slow = slow!.next;         // Move one step
        fast = fast.next.next;     // Move two steps
        
        if (slow === fast) {
            // Pointers met—cycle exists!
            return true;
        }
    }
    
    // Fast reached null—no cycle
    return false;
}
 
// Extended: Find the start of the cycle
function findCycleStart<T>(
    head: LinkedNode<T> | null
): LinkedNode<T> | null {
    if (head === null || head.next === null) {
        return null;
    }
    
    let slow: LinkedNode<T> | null = head;
    let fast: LinkedNode<T> | null = head;
    
    // Phase 1: Detect if cycle exists
    while (fast !== null && fast.next !== null) {
        slow = slow!.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            break; // Cycle detected
        }
    }
    
    // No cycle found
    if (fast === null || fast.next === null) {
        return null;
    }
    
    // Phase 2: Find the start of the cycle
    // Reset one pointer to head
    slow = head;
    
    // Move both pointers one step at a time
    // They will meet at the cycle start!
    while (slow !== fast) {
        slow = slow!.next;
        fast = fast!.next;
    }
    
    return slow;
}
 
// Count the length of the cycle
function getCycleLength<T>(head: LinkedNode<T> | null): number {
    const cycleStart = findCycleStart(head);
    if (cycleStart === null) {
        return 0;
    }
    
    let count = 1;
    let current = cycleStart.next;
    
    while (current !== cycleStart) {
        count++;
        current = current!.next;
    }
    
    return count;
}

Floyd's Algorithm Complexity
Operation	Time Complexity	Space Complexity
Detect cycle	O(n)	O(1)
Find cycle start	O(n)	O(1)
Count cycle length	O(n)	O(1)

The Power of Two Pointers

Floyd's algorithm is a fundamental technique that appears throughout DSA. It's used for cycle detection, finding middle elements, and various other linked list problems. The key insight—using different speeds to derive information about the structure—is applicable beyond just linked lists.

Choosing the Right Technique

With multiple techniques available, how do you choose the right one? The decision depends on several factors:

Decision Matrix for End Detection
Scenario	Best Technique	Why
Known circular list, need full traversal	Entry Point Comparison	Simple, O(1) space, idiomatic
Circular list with size counter	Count-Based	Avoids reference comparison, easy partial traversals
Using sentinel-based implementation	Sentinel Comparison	Leverages existing structure, familiar while-loop pattern
Unknown list, need cycle detection	Floyd's Algorithm	O(1) space, handles linear and circular lists
Need to find cycle start/length	Floyd's (Phase 2)	Can determine exact cycle characteristics
Need general visited tracking	Visited Set	Most flexible, handles complex structures
Memory-constrained environment	Floyd's or Entry Point	Both are O(1) space

Use Entry Point Comparison When

•You control the data structure design
•You have a clear starting point
•You need simple, maintainable code
•Standard traversal is the goal

Use Floyd's Algorithm When

•You receive an unknown list
•You need to detect if a cycle exists
•Memory is constrained (O(1) required)
•LeetCode/interview cycle problems

Default Choice

For most circular linked list implementations that you control, entry point comparison (do-while pattern) is the default choice. It's simple, efficient, and clearly expresses the intent. Use other techniques when you have specific requirements that demand them.

Summary: Detecting the End Condition

We've comprehensively explored the challenge of termination in circular linked lists. Let's consolidate the key learnings:

Key Takeaways

•The Infinite Loop Trap — Circular lists have no null terminator. The naive 'while (current !== null)' pattern causes infinite loops.
•Entry Point Comparison — The most common technique. Use do-while (or flag) to visit the starting node before checking if you've returned to it.
•Count-Based Termination — When you have a size counter, simply visit exactly 'size' nodes. Enables easy partial traversals and cycle counting.
•Sentinel Nodes — A dedicated marker node provides a consistent stopping point, enabling familiar while-loop patterns.
•Visited Tracking — Use a hash set for O(n) space cycle detection when you don't know the structure in advance.
•Floyd's Algorithm — O(1) space cycle detection using two pointers at different speeds. Can also find cycle start and length.
•Choose Based on Context — Entry point comparison for controlled implementations, Floyd's for unknown lists, sentinels for simplified code.

The Golden Rule:

Before writing any traversal code for a circular linked list, ask yourself: "What is my termination condition?" The answer should be explicit in your code, not left to chance. Whether you're comparing to a starting point, counting iterations, checking for a sentinel, or using two pointers—make the stopping logic clear and deliberate.

Module Complete:

You've now mastered circular linked lists! You understand what they are, their singly and doubly circular variants, real-world applications, and the critical techniques for handling the circular nature—especially how to detect when you've completed a cycle. This knowledge prepares you for advanced linked list patterns and the next data structures in your DSA journey.

Module Complete

Congratulations! You've completed Module 8: Circular Linked Lists. You understand circular structures conceptually, can implement both singly and doubly circular variants, know when to use them in practice, and can successfully handle the termination challenge. You're ready to tackle any circular linked list problem with confidence.

4 / 4

Loading learning content...

Data Structures & AlgorithmsCircular Linked Lists

Circular Linked Lists

LevelIntermediate

Duration55 mins

TopicCircular Linked Lists

4 / 4

Detecting the End Condition

The Infinite Loop Trap

In linear linked lists, termination is trivial: follow next pointers until you hit null. The language of the code is simple:

while (current !== null) {
    // process current
    current = current.next;
}

This is the defining challenge of working with circular structures: How do we know when to stop?

What You Will Master

The Fundamental Challenge

Let's deeply understand why the termination problem exists and what makes it different from linear lists.

Linear List Termination:

head → [A] → [B] → [C] → [D] → null

Circular List Non-Termination:

head → [A] → [B] → [C] → [D] ─┐
        ↑                      │
        └──────────────────────┘

Following next pointers from any node will never encounter null. You'll visit A, B, C, D, A, B, C, D, A... indefinitely. The structure is continuous; there is no built-in termination signal.

The Core Question:

Since the structure doesn't tell us when to stop, we must introduce external knowledge or markers to detect cycle completion. The techniques fall into several categories:

Termination Detection Approaches

•Entry Point Comparison — Remember where you started; stop when you return to it
•Count-Based Termination — Know how many elements exist; stop after visiting that many
•Marker-Based Detection — Use a special value or flag to indicate the starting point
•Visited Tracking — Maintain a set of visited nodes; stop when you revisit one
•Two-Pointer Techniques — Use the fast/slow pointer approach to detect cycles

The Classic Bug

Entry Point Comparison (Do-While Pattern)

The most common and idiomatic approach is entry point comparison: remember the starting node, traverse the list, and stop when you return to that starting node.

The Do-While Pattern:

In languages with do-while loops, the pattern is elegant:

do {
    // Process current
    current = current.next;
} while (current !== startNode);

Entry Point Comparison Traversal
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// Technique 1: Do-While with Entry Point Comparison
function traverseWithDoWhile<T>(head: CircularNode<T> | null): T[] {
    if (head === null) {
        return [];
    }
    
    const result: T[] = [];
    let current = head;
    
    // Do-while: visit node before checking termination
    do {
        result.push(current.data);
        current = current.next;
    } while (current !== head);  // Stop when we return to start
    
    return result;
}
 
// Why do-while and not while?
// Consider this buggy version:
function buggyTraversal<T>(head: CircularNode<T> | null): T[] {
    if (head === null) {
        return [];
    }
    
    const result: T[] = [];
    let current = head;
    
    // BUG: This checks BEFORE processing the first node
    while (current !== head) {  // Immediately false! current IS head
        result.push(current.data);
        current = current.next;
    }
    
    // This returns [] even for a non-empty list!
    return result;
}
 
// Alternative: Use a flag for languages without do-while
function traverseWithFlag<T>(head: CircularNode<T> | null): T[] {
    if (head === null) {
        return [];
    }
    
    const result: T[] = [];
    let current: CircularNode<T> | null = head;
    let isFirst = true;
    
    while (isFirst || current !== head) {
        isFirst = false;
        result.push(current!.data);
        current = current!.next;
    }
    
    return result;
}

When to Use This Technique

Count-Based Termination

If you maintain a size counter in your circular linked list implementation, you can use count-based termination: visit exactly size nodes and then stop.

Advantages over Entry Point Comparison:

No reference comparison — Some node types might not support equality checks efficiently
Works for partial traversals — Easy to visit only the first N elements
Loop counting — Easy to determine how many cycles you've completed

Disadvantages:

Requires accurate size — If size is wrong, behavior is wrong
Maintenance overhead — Must update size on every insert/delete

Count-Based Termination
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Technique 2: Count-Based Termination
class CircularListWithSize<T> {
    head: CircularNode<T> | null = null;
    size: number = 0;
    
    // Traverse exactly 'size' elements
    traverse(): T[] {
        if (this.head === null || this.size === 0) {
            return [];
        }
        
        const result: T[] = [];
        let current = this.head;
        
        for (let i = 0; i < this.size; i++) {
            result.push(current.data);
            current = current.next;
        }
        
        return result;
    }
    
    // Visit first N elements (with wraparound if N > size)
    visitN(n: number): T[] {
        if (this.head === null || this.size === 0) {
            return [];
        }
        
        const result: T[] = [];
        let current = this.head;
        
        for (let i = 0; i < n; i++) {
            result.push(current.data);
            current = current.next;
        }
        
        return result;
    }
    
    // Complete K full cycles
    traverseKCycles(k: number): T[] {
        if (this.head === null || this.size === 0) {
            return [];
        }
        
        const totalVisits = this.size * k;
        const result: T[] = [];
        let current = this.head;
        
        for (let i = 0; i < totalVisits; i++) {
            result.push(current.data);
            current = current.next;
        }
        
        return result;
    }
    
    // Find element at logical index (with wraparound)
    getAt(index: number): T | null {
        if (this.head === null || this.size === 0) {
            return null;
        }
        
        // Handle negative indices and indices > size with modulo
        const normalizedIndex = ((index % this.size) + this.size) % this.size;
        
        let current = this.head;
        for (let i = 0; i < normalizedIndex; i++) {
            current = current.next;
        }
        
        return current.data;
    }
}
 
// Example: Demonstrate count-based access
const list = new CircularListWithSize<string>();
// Assume list has: A → B → C → D → (back to A), size = 4
 
// list.getAt(0)  → A
// list.getAt(3)  → D
// list.getAt(4)  → A (wraps around)
// list.getAt(10) → C (wraps: 10 % 4 = 2)
// list.getAt(-1) → D (wraps: (-1 % 4 + 4) % 4 = 3)

Modular Arithmetic and Circular Access

Sentinel or Marker-Based Detection

Another approach is to use a sentinel marker to identify the 'start' of the list. This can be:

A dedicated sentinel node — A special node that doesn't hold real data
A marked data value — A reserved value that signals 'this is the start'
A modification to the starting node — Temporarily mark it during traversal

Sentinel Node Approach:

With a sentinel node, the list has one node that's always identifiable as the entry/exit point. The 'real' head is sentinel.next, and the 'real' tail is sentinel.prev (in doubly circular lists).

When traversing, you start at sentinel.next and stop when you reach sentinel again, rather than comparing to your starting point.

Sentinel-Based Traversal
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// Technique 3: Sentinel Node for End Detection
class CircularListWithSentinel<T> {
    private sentinel: CircularNode<T>;
    
    constructor() {
        // Sentinel with a recognizable marker (null data in this case)
        this.sentinel = {
            data: null as unknown as T,
            next: null as unknown as CircularNode<T>,
        };
        // Sentinel points to itself in an empty list
        this.sentinel.next = this.sentinel;
    }
    
    isEmpty(): boolean {
        return this.sentinel.next === this.sentinel;
    }
    
    insertAfterSentinel(data: T): void {
        const newNode: CircularNode<T> = {
            data,
            next: this.sentinel.next,
        };
        this.sentinel.next = newNode;
    }
    
    // Traverse using sentinel as the stopping point
    traverse(): T[] {
        const result: T[] = [];
        let current = this.sentinel.next;
        
        // Stop when we reach the sentinel
        while (current !== this.sentinel) {
            result.push(current.data);
            current = current.next;
        }
        
        return result;
    }
    
    // Search for a value
    find(value: T): CircularNode<T> | null {
        let current = this.sentinel.next;
        
        while (current !== this.sentinel) {
            if (current.data === value) {
                return current;
            }
            current = current.next;
        }
        
        return null; // Not found
    }
}
 
// Note: With a sentinel, we CAN use while loop!
// The sentinel acts like null in linear lists—it terminates traversal.

The Sentinel Advantage

Visited Tracking with External Memory

When you don't have a known starting point or when detecting cycles in an unknown structure, you may need to track which nodes you've visited using external memory (a hash set, for example).

Use Cases:

Cycle detection in unknown lists — You receive a list and don't know if it's circular
Multiple traversals from different starting points — Need to avoid revisiting
Graph-like structures — Nodes might be reachable from multiple paths

Trade-off:

This approach uses O(n) additional space but provides O(1) lookup per node. It's overkill for simple circular list traversal but essential for more complex scenarios.

Visited Tracking
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Technique 4: Visited Set Tracking
function traverseWithVisitedSet<T>(startNode: CircularNode<T> | null): T[] {
    if (startNode === null) {
        return [];
    }
    
    const result: T[] = [];
    const visited = new Set<CircularNode<T>>();
    let current: CircularNode<T> | null = startNode;
    
    while (current !== null && !visited.has(current)) {
        visited.add(current);
        result.push(current.data);
        current = current.next;
    }
    
    return result;
}
 
// More useful: Cycle detection in an unknown list
interface Node<T> {
    data: T;
    next: Node<T> | null;
}
 
function detectCycleWithSet<T>(head: Node<T> | null): {
    hasCycle: boolean;
    cycleStart: Node<T> | null;
} {
    if (head === null) {
        return { hasCycle: false, cycleStart: null };
    }
    
    const visited = new Set<Node<T>>();
    let current: Node<T> | null = head;
    
    while (current !== null) {
        if (visited.has(current)) {
            // We've seen this node before—cycle detected!
            return { hasCycle: true, cycleStart: current };
        }
        visited.add(current);
        current = current.next;
    }
    
    // Reached null—no cycle
    return { hasCycle: false, cycleStart: null };
}
 
// Complexity Analysis:
// Time: O(n) — each node visited once
// Space: O(n) — storing all visited nodes

Memory Overhead

Floyd's Cycle Detection (Tortoise and Hare)

The Algorithm:

Initialize two pointers at the head: slow (tortoise) and fast (hare)
Move slow one step at a time, fast two steps at a time
If there's no cycle, fast will reach null
If there's a cycle, fast will eventually catch up to slow inside the cycle

Why It Works:

Mathematical Insight:

Once both pointers are in the cycle, the distance between them decreases by 1 with each step (fast gains 2 - 1 = 1 position per iteration). Therefore, they must meet within the length of the cycle.

Floyd's Cycle Detection
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// Floyd's Cycle Detection Algorithm
interface LinkedNode<T> {
    data: T;
    next: LinkedNode<T> | null;
}
 
function detectCycleFloyd<T>(head: LinkedNode<T> | null): boolean {
    if (head === null || head.next === null) {
        return false;
    }
    
    let slow: LinkedNode<T> | null = head;
    let fast: LinkedNode<T> | null = head;
    
    while (fast !== null && fast.next !== null) {
        slow = slow!.next;         // Move one step
        fast = fast.next.next;     // Move two steps
        
        if (slow === fast) {
            // Pointers met—cycle exists!
            return true;
        }
    }
    
    // Fast reached null—no cycle
    return false;
}
 
// Extended: Find the start of the cycle
function findCycleStart<T>(
    head: LinkedNode<T> | null
): LinkedNode<T> | null {
    if (head === null || head.next === null) {
        return null;
    }
    
    let slow: LinkedNode<T> | null = head;
    let fast: LinkedNode<T> | null = head;
    
    // Phase 1: Detect if cycle exists
    while (fast !== null && fast.next !== null) {
        slow = slow!.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            break; // Cycle detected
        }
    }
    
    // No cycle found
    if (fast === null || fast.next === null) {
        return null;
    }
    
    // Phase 2: Find the start of the cycle
    // Reset one pointer to head
    slow = head;
    
    // Move both pointers one step at a time
    // They will meet at the cycle start!
    while (slow !== fast) {
        slow = slow!.next;
        fast = fast!.next;
    }
    
    return slow;
}
 
// Count the length of the cycle
function getCycleLength<T>(head: LinkedNode<T> | null): number {
    const cycleStart = findCycleStart(head);
    if (cycleStart === null) {
        return 0;
    }
    
    let count = 1;
    let current = cycleStart.next;
    
    while (current !== cycleStart) {
        count++;
        current = current!.next;
    }
    
    return count;
}

Floyd's Algorithm Complexity
Operation	Time Complexity	Space Complexity
Detect cycle	O(n)	O(1)
Find cycle start	O(n)	O(1)
Count cycle length	O(n)	O(1)

The Power of Two Pointers

Choosing the Right Technique

With multiple techniques available, how do you choose the right one? The decision depends on several factors:

Decision Matrix for End Detection
Scenario	Best Technique	Why
Known circular list, need full traversal	Entry Point Comparison	Simple, O(1) space, idiomatic
Circular list with size counter	Count-Based	Avoids reference comparison, easy partial traversals
Using sentinel-based implementation	Sentinel Comparison	Leverages existing structure, familiar while-loop pattern
Unknown list, need cycle detection	Floyd's Algorithm	O(1) space, handles linear and circular lists
Need to find cycle start/length	Floyd's (Phase 2)	Can determine exact cycle characteristics
Need general visited tracking	Visited Set	Most flexible, handles complex structures
Memory-constrained environment	Floyd's or Entry Point	Both are O(1) space

Use Entry Point Comparison When

•You control the data structure design
•You have a clear starting point
•You need simple, maintainable code
•Standard traversal is the goal

Use Floyd's Algorithm When

•You receive an unknown list
•You need to detect if a cycle exists
•Memory is constrained (O(1) required)
•LeetCode/interview cycle problems

Default Choice

Summary: Detecting the End Condition

We've comprehensively explored the challenge of termination in circular linked lists. Let's consolidate the key learnings:

Key Takeaways

•The Infinite Loop Trap — Circular lists have no null terminator. The naive 'while (current !== null)' pattern causes infinite loops.
•Entry Point Comparison — The most common technique. Use do-while (or flag) to visit the starting node before checking if you've returned to it.
•Count-Based Termination — When you have a size counter, simply visit exactly 'size' nodes. Enables easy partial traversals and cycle counting.
•Sentinel Nodes — A dedicated marker node provides a consistent stopping point, enabling familiar while-loop patterns.
•Visited Tracking — Use a hash set for O(n) space cycle detection when you don't know the structure in advance.
•Floyd's Algorithm — O(1) space cycle detection using two pointers at different speeds. Can also find cycle start and length.
•Choose Based on Context — Entry point comparison for controlled implementations, Floyd's for unknown lists, sentinels for simplified code.

The Golden Rule:

Module Complete:

Module Complete

4 / 4