Detect if a Linked List is Circular in DSA Typescript - Deep Dive

Overview - Detect if a Linked List is Circular

What is it?

A circular linked list is a special type of linked list where the last node points back to one of the previous nodes, forming a loop. Detecting if a linked list is circular means checking whether such a loop exists. This helps avoid infinite loops when traversing the list. Understanding this concept is important for safe and efficient linked list operations.

Why it matters

Without detecting circular linked lists, programs can get stuck in endless loops when trying to process or print the list. This can cause crashes or freezes in software. Detecting circularity helps prevent these problems and ensures data structures behave as expected. It also helps in debugging and designing algorithms that work with linked lists.

Where it fits

Before learning this, you should understand what a linked list is and how it works. After this, you can learn about advanced linked list operations like reversing, merging, or detecting cycles with more complex algorithms. This topic is a stepping stone to understanding graph cycles and memory management.

Mental Model

Core Idea

A linked list is circular if you can start at the head and follow next links forever without reaching a null end.

Think of it like...

Imagine walking down a path where each signpost points to the next one. If you eventually come back to a signpost you've seen before, the path loops in a circle.

Head -> Node1 -> Node2 -> Node3
                 ↑           ↓
                 ←←←←←←←←←←←

Build-Up - 6 Steps

1

Foundation

Understanding Linked List Basics

Concept: Learn what a linked list is and how nodes connect.

A linked list is a chain of nodes where each node holds data and a reference to the next node. The last node usually points to null, marking the end. For example, Node1 -> Node2 -> Node3 -> null means the list ends at Node3.

Result

You can traverse the list from head to end by following next pointers until you reach null.

Understanding the normal end of a linked list is key to spotting when something unusual, like a loop, happens.

2

Foundation

What Makes a Linked List Circular

Concept: Recognize how a loop forms in a linked list.

If a node's next pointer points back to a previous node instead of null, the list forms a circle. For example, Node3 -> Node2 creates a loop: Node2 -> Node3 -> Node2 -> ... This means traversing never ends.

Result

The list has no end and cycles through some nodes repeatedly.

Knowing how loops form helps you understand why normal traversal can get stuck.

3

Intermediate

Simple Loop Detection by Marking Nodes

🤔Before reading on: Do you think marking nodes visited is a good way to detect loops? Commit to yes or no.

Concept: Use extra memory to remember visited nodes during traversal.

Start at the head and move through nodes. Keep a set of visited nodes. If you reach a node already in the set, a loop exists. If you reach null, no loop. This method uses extra space but is easy to understand.

Result

Detects loops correctly but uses extra memory proportional to list size.

Understanding this method shows the tradeoff between simplicity and memory use.

4

Intermediate

Floyd's Cycle Detection Algorithm

🤔Before reading on: Do you think two pointers moving at different speeds can detect a loop? Commit to yes or no.

Concept: Use two pointers moving at different speeds to find loops without extra memory.

Use a slow pointer moving one step at a time and a fast pointer moving two steps. If the list has a loop, the fast pointer will eventually catch up to the slow pointer inside the loop. If the fast pointer reaches null, no loop exists.

Result

Detects loops efficiently using constant memory and linear time.

Knowing this algorithm helps write efficient loop detection without extra space.

5

Advanced

Implementing Loop Detection in TypeScript

🤔Before reading on: Can you predict the output of the code when the list is circular or not? Commit to your answer.

Concept: Write runnable TypeScript code to detect circular linked lists using Floyd's algorithm.

class Node { data: number; next: Node | null; constructor(data: number) { this.data = data; this.next = null; } } function isCircular(head: Node | null): boolean { if (!head) return false; let slow: Node | null = head; let fast: Node | null = head.next; while (fast !== null && fast.next !== null) { if (slow === fast) return true; slow = slow!.next; fast = fast.next.next; } return false; } // Example usage: const node1 = new Node(1); const node2 = new Node(2); const node3 = new Node(3); node1.next = node2; node2.next = node3; node3.next = node1; // Creates a loop console.log(isCircular(node1)); // true const node4 = new Node(4); node3.next = node4; // Break loop node4.next = null; console.log(isCircular(node1)); // false

Result

First console.log prints true because of the loop; second prints false after breaking the loop.

Seeing the code in action solidifies understanding of how the algorithm works in practice.

6

Expert

Detecting Loop Start Node and Length

🤔Before reading on: Can you guess how to find the exact node where the loop starts after detection? Commit to your answer.

Concept: Extend Floyd's algorithm to find the loop's entry point and its length.

After slow and fast pointers meet inside the loop, reset slow to head. Move both pointers one step at a time; where they meet again is the loop start. To find loop length, keep one pointer fixed and move the other until it returns to the same node, counting steps.

Result

You can identify the exact node where the loop begins and how many nodes are in the loop.

Knowing loop start and length helps in advanced linked list manipulations and debugging.

Under the Hood

Floyd's algorithm works because the fast pointer moves twice as fast as the slow pointer. If a loop exists, the fast pointer laps the slow pointer inside the loop, causing them to meet. This meeting proves a cycle. Resetting one pointer to head and moving both at the same speed exploits the distance properties of the loop to find its start.

Why designed this way?

This method was designed to detect cycles efficiently without extra memory. Earlier methods used extra space or were slower. Floyd's algorithm balances speed and memory use, making it ideal for real-world applications where memory is limited.

Head
 ↓
[Node1] -> [Node2] -> [Node3] -> [Node4]
               ↑                 ↓
               ←←←←←←←←←←←←←←←←

Myth Busters - 3 Common Misconceptions

Quick: Does reaching a null pointer always mean the list is not circular? Commit to yes or no.

Common Belief: If you reach null while traversing, the list is definitely not circular.

Reality: True, but only if traversal is done correctly. If traversal skips nodes or pointers are corrupted, null might be missed or misinterpreted.

Why it matters: Assuming null means no loop without careful traversal can cause missed loops or crashes.

Quick: Can a linked list have multiple loops? Commit to yes or no.

Common Belief: A linked list can have multiple separate loops.

Reality: A singly linked list can have only one loop because each node points to only one next node, so loops merge into one cycle.

Why it matters: Expecting multiple loops can confuse debugging and algorithm design.

Quick: Does marking nodes visited always work without problems? Commit to yes or no.

Common Belief: Using extra memory to mark visited nodes is always the best way to detect loops.

Reality: It works but uses extra memory and can be inefficient for large lists. Floyd's algorithm is better for memory efficiency.

Why it matters: Choosing inefficient methods can cause performance issues in large-scale systems.

Expert Zone

1

Floyd's algorithm can be adapted to detect cycles in other data structures like graphs with minor changes.

2

The meeting point inside the loop is not necessarily the loop start, but it provides a key to find it.

3

In some languages, pointer equality checks must be done carefully to avoid false negatives due to object references.

When NOT to use

Avoid using Floyd's algorithm if you need to modify the list during detection or if nodes don't have reliable next pointers. In such cases, using hash sets or other marking methods might be safer.

Production Patterns

In production, loop detection is used in garbage collectors to detect reference cycles, in network routing to detect loops, and in debugging tools to find infinite loops in data structures.

Connections

Graph Cycle Detection

Builds-on

Understanding linked list cycles helps grasp cycle detection in graphs, which is more complex but uses similar principles.

Memory Management

Related concept

Detecting circular references in linked lists is similar to detecting memory leaks caused by reference cycles in programming languages.

Traffic Roundabouts

Analogous system

Traffic roundabouts create loops in road networks; understanding how cars enter and exit helps visualize how loops form and are detected in linked lists.

Common Pitfalls

#1 Assuming the list is circular if slow and fast pointers never meet.

Wrong approach:

function isCircular(head) {
let slow = head;
let fast = head.next;
while (fast !== null && fast.next !== null) {
if (slow === fast) return true;
slow = slow.next;
fast = fast.next.next;
}
return true; // Wrong: returns true even if no loop
}

Correct approach:

function isCircular(head) {
let slow = head;
let fast = head.next;
while (fast !== null && fast.next !== null) {
if (slow === fast) return true;
slow = slow.next;
fast = fast.next.next;
}
return false; // Correct: returns false if no loop
}

Root cause:

Misunderstanding the loop exit condition causes always returning true.

#2 Modifying the list nodes during detection, breaking the structure.

Wrong approach:

function isCircular(head) {
let current = head;
while (current !== null) {
if (current.visited) return true;
current.visited = true; // Modifies node
current = current.next;
}
return false;
}

Correct approach:

Use external data structures like a Set to track visited nodes without modifying them:
function isCircular(head) {
const visited = new Set();
let current = head;
while (current !== null) {
if (visited.has(current)) return true;
visited.add(current);
current = current.next;
}
return false;
}

Root cause:

Altering node properties can corrupt data and cause bugs.

Key Takeaways

A circular linked list loops back to an earlier node, causing infinite traversal if unchecked.

Floyd's cycle detection algorithm uses two pointers moving at different speeds to detect loops efficiently without extra memory.

Detecting the start of the loop and its length helps in advanced linked list operations and debugging.

Simple methods using extra memory exist but are less efficient than Floyd's algorithm.

Understanding loop detection is essential for safe linked list use and connects to broader concepts like graph cycles and memory management.

Practice

1. What does it mean if a linked list is circular?

easy

A. The last node points back to one of the previous nodes, forming a loop

B. The linked list has no nodes

C. The linked list nodes are sorted in ascending order

D. The linked list has only one node

Solution

1. Step 1: Understand linked list structure

   A linked list is a chain of nodes where each node points to the next node.

2. Step 2: Define circular linked list

   If the last node points back to any previous node, it creates a loop, making the list circular.

3. Final Answer:

   The last node points back to one of the previous nodes, forming a loop -> Option A

4. Quick Check:

   Circular linked list = last node points back [OK]

Hint: Circular means last node links back to earlier node [OK]

Common Mistakes:

• Thinking circular means sorted
• Confusing empty list with circular
• Assuming single node list is always circular

2. Which TypeScript code snippet correctly checks if a linked list is circular using two pointers?

easy

A. for(let node = head; node != null; node = node.next) { if(node.next === head) return true; } return false;

B. let slow = head; while(slow) { slow = slow.next; if(slow === head) return true; } return false;

C. let slow = head; let fast = head; while(fast && fast.next) { slow = slow.next; fast = fast.next.next; if(slow === fast) return true; } return false;

D. let current = head; while(current.next) { current = current.next; } return current === null;

Solution

1. Step 1: Understand Floyd's cycle detection

   Use two pointers: slow moves 1 step, fast moves 2 steps. If they meet, list is circular.

2. Step 2: Analyze code snippets

   let slow = head; let fast = head; while(fast && fast.next) { slow = slow.next; fast = fast.next.next; if(slow === fast) return true; } return false; correctly implements this logic with proper conditions and pointer moves.

3. Final Answer:

   let slow = head; let fast = head; while(fast && fast.next) { slow = slow.next; fast = fast.next.next; if(slow === fast) return true; } return false; -> Option C

4. Quick Check:

   Two pointers meet means circular [OK]

Hint: Use slow and fast pointers to detect loop [OK]

Common Mistakes:

• Moving fast pointer only one step
• Not checking fast and fast.next for null
• Returning false too early

3. What will be the output of this TypeScript code snippet?

class Node { constructor(public val: number, public next: Node | null = null) {} }
const head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = head.next;
function isCircular(head: Node | null): boolean {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}
console.log(isCircular(head));

medium

A. true

B. false

C. undefined

D. Runtime error

Solution

1. Step 1: Understand the linked list structure

   Nodes 1 -> 2 -> 3, then 3 points back to node 2, creating a loop.

2. Step 2: Trace the two-pointer loop detection

   Slow and fast pointers will meet inside the loop, so function returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Loop exists, so output is true [OK]

Hint: Loop in list makes function return true [OK]

Common Mistakes:

• Assuming no loop because list looks linear
• Confusing node references
• Ignoring pointer equality check

4. Identify the bug in this TypeScript function meant to detect a circular linked list:

function isCircular(head: Node | null): boolean {
  let slow = head;
  let fast = head;
  while (fast !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

medium

A. The function should use a for loop instead of while

B. The slow pointer should move two steps instead of one

C. The function should return false inside the loop

D. The while loop should check fast and fast.next for null before moving pointers

Solution

1. Step 1: Analyze pointer movement safety

   fast.next.next is accessed without checking if fast.next is null, risking runtime error.

2. Step 2: Correct loop condition

   Loop should check both fast and fast.next are not null before moving pointers to avoid errors.

3. Final Answer:

   The while loop should check fast and fast.next for null before moving pointers -> Option D

4. Quick Check:

   Check fast and fast.next to avoid errors [OK]

Hint: Always check fast and fast.next before advancing fast [OK]

Common Mistakes:

• Not checking fast.next before fast.next.next
• Moving slow pointer incorrectly
• Returning false too early

5. Given a singly linked list where the last node might point to any node in the list or null, how would you modify the detection function to also return the node where the cycle begins if it is circular?
Which approach correctly finds the start of the loop?

hard

A. Count the number of nodes and return the middle node as the start of the loop

B. After detecting the cycle, reset one pointer to head and move both pointers one step at a time until they meet; the meeting point is the start of the loop

C. Use a hash set to store visited nodes and return the first repeated node found

D. Reverse the linked list and check if the head changes to detect the loop start

Solution

1. Step 1: Detect cycle using two pointers

   Use Floyd's algorithm to find if slow and fast pointers meet inside the loop.

2. Step 2: Find loop start node

   Reset one pointer to head, move both pointers one step at a time; their meeting point is the loop start.

3. Final Answer:

   After detecting the cycle, reset one pointer to head and move both pointers one step at a time until they meet; the meeting point is the start of the loop -> Option B

4. Quick Check:

   Reset pointer and move both to find loop start [OK]

Hint: Reset pointer after cycle detection to find loop start [OK]

Common Mistakes:

• Assuming middle node is loop start
• Using node count instead of pointers
• Trying to reverse list to find loop