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

Overview - Detect if a Linked List is Circular

What is it?

A circular linked list is a chain of nodes 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 processing the list. Understanding this concept is key to safely working with linked lists.

Why it matters

Without detecting circular linked lists, programs can get stuck in endless loops, causing crashes or freezes. This problem affects many real-world applications like network routing, task scheduling, and memory management. Detecting circularity ensures programs run smoothly and data structures behave as expected.

Where it fits

Before this, learners should understand what a linked list is and how nodes connect. After this, they can learn about removing loops, advanced linked list operations, and graph cycle detection.

Mental Model

Core Idea

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

Think of it like...

Imagine walking down a path where each step leads to the next. If you eventually step onto a path you've already walked, you are in a loop, like a circular linked list.

Head -> Node1 -> Node2 -> Node3 -> Node4
                     ↑                   |
                     |-------------------|

Build-Up - 6 Steps

1

Foundation

Understand Linked List Structure

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

A linked list is a sequence of nodes. Each node holds data and a pointer to the next node. The last node usually points to null, marking the end.

Result

You can visualize a linked list as a chain of nodes ending with null.

Knowing the basic linked list structure is essential before detecting loops.

2

Foundation

What Makes a List Circular

Concept: Identify how a linked list becomes circular by having a node point back to a previous node.

If any node's next pointer points to an earlier node instead of null, the list forms a loop. This means traversing the list never ends.

Result

A circular linked list has no null end and loops back on itself.

Recognizing the loop condition helps understand why detection is needed.

3

Intermediate

Naive Loop Detection by Visited Nodes

🤔Before reading on: Do you think storing visited nodes is efficient for large lists? Commit to your answer.

Concept: Use extra memory to track nodes visited during traversal to detect loops.

Traverse the list, storing each visited node in a set. If you visit a node already in the set, a loop exists. If you reach null, no loop.

Result

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

This method works but is not memory efficient for large lists.

4

Intermediate

Floyd's Cycle Detection Algorithm

🤔Before reading on: Will two pointers moving at different speeds always meet if a loop exists? Commit to yes or no.

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

Use a slow pointer moving one step and a fast pointer moving two steps. If they meet, a loop exists. If fast pointer reaches null, no loop.

Result

Efficient loop detection with O(1) memory and O(n) time.

Using two pointers cleverly avoids extra memory while reliably detecting loops.

5

Advanced

Implementing Detection in JavaScript

🤔Before reading on: Do you think the fast pointer can skip over the slow pointer without meeting? Commit to yes or no.

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

```javascript class Node { constructor(value) { this.value = value; this.next = null; } } function isCircular(head) { if (!head) return false; let slow = head; let fast = head.next; while (fast && fast.next) { if (slow === fast) return true; slow = slow.next; fast = fast.next.next; } return false; } // Example usage: const a = new Node(1); const b = new Node(2); const c = new Node(3); a.next = b; b.next = c; c.next = a; // creates a loop console.log(isCircular(a)); // true const x = new Node(10); const y = new Node(20); x.next = y; y.next = null; console.log(isCircular(x)); // false ```

Result

true false

Seeing the code in action solidifies understanding of the algorithm and its correctness.

6

Expert

Why Fast Pointer Moves Two Steps

🤔Before reading on: Why does the fast pointer move two steps instead of one? Commit to your reasoning.

Concept: Understand the reasoning behind the fast pointer's speed in Floyd's algorithm.

The fast pointer moves two steps to catch up with the slow pointer inside the loop. If both moved one step, they would stay in sync and never meet. The speed difference guarantees meeting if a loop exists.

Result

The pointers meet inside the loop, confirming circularity.

Understanding pointer speeds explains why the algorithm is both efficient and reliable.

Under the Hood

Floyd's algorithm uses two pointers moving at different speeds through the linked list nodes. If the list has a loop, the fast pointer will eventually lap the slow pointer inside the loop, causing them to meet. If no loop exists, the fast pointer reaches the end (null) first. This works because the fast pointer covers more ground and cycles through the loop faster than the slow pointer.

Why designed this way?

This method was designed to detect loops without extra memory, unlike the naive approach that stores visited nodes. It balances time efficiency and minimal memory use, making it practical for large or memory-constrained systems. Alternatives like hashing nodes were rejected due to higher memory costs.

Head
  ↓
+------+     +------+     +------+     +------+
| Node | --> | Node | --> | Node | --> | Node |
+------+     +------+     +------+     +------+
               ↑                         |
               |-------------------------|

Slow pointer moves 1 step
Fast pointer moves 2 steps
They meet inside the loop

Myth Busters - 3 Common Misconceptions

Quick: Does a circular linked list always loop back to the head node? Commit yes or no.

Common Belief: A circular linked list always loops back to the first node (head).

Reality: The loop can start at any node, not necessarily the head.

Why it matters: Assuming the loop starts at the head can cause incorrect detection or removal logic.

Quick: Can the fast pointer skip over the slow pointer without meeting? Commit yes or no.

Common Belief: The fast pointer might skip the slow pointer and never meet, causing false negatives.

Reality: Because the fast pointer moves two steps and the slow one step, they will always meet if a loop exists.

Why it matters: Believing this can lead to mistrust of Floyd's algorithm and unnecessary complex solutions.

Quick: Is extra memory always needed to detect loops? Commit yes or no.

Common Belief: You must store visited nodes to detect loops.

Reality: Floyd's algorithm detects loops without extra memory.

Why it matters: Not knowing this leads to inefficient solutions that waste memory.

Expert Zone

1

The meeting point of slow and fast pointers is not necessarily the start of the loop; additional steps are needed to find the loop's entry.

2

If the list is very large and the loop is near the end, the fast pointer may take many iterations before meeting slow, affecting performance.

3

Modifying the list during detection (like changing pointers) can break the algorithm, so detection should be done on a stable list.

When NOT to use

Avoid Floyd's algorithm if you need to find the exact start of the loop immediately; use extended algorithms that locate the loop entry. Also, if the list nodes lack pointer equality (e.g., in some functional languages), alternative detection methods are needed.

Production Patterns

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

Connections

Graph Cycle Detection

Builds-on

Detecting loops in linked lists is a simpler case of cycle detection in graphs, helping understand more complex data structures.

Tortoise and Hare Algorithm

Same pattern

Floyd's cycle detection is also known as the Tortoise and Hare algorithm, illustrating how two pointers moving at different speeds can solve problems efficiently.

Traffic Roundabouts

Analogous system

Traffic roundabouts where cars circle until exiting resemble circular linked lists, helping understand how loops cause repeated traversal.

Common Pitfalls

#1 Checking only if fast pointer is null without checking fast.next causes runtime errors.

Wrong approach:

while (fast !== null) {
if (slow === fast) return true;
slow = slow.next;
fast = fast.next.next;
}

Correct approach:

while (fast !== null && fast.next !== null) {
if (slow === fast) return true;
slow = slow.next;
fast = fast.next.next;
}

Root cause:

Not verifying fast.next exists before accessing fast.next.next leads to errors when fast is at the last node.

#2 Starting fast pointer at head instead of head.next can cause immediate false positive if head equals fast initially.

Wrong approach:

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

Correct approach:

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

Root cause:

Starting both pointers at the same node causes immediate equality before moving, falsely detecting a loop.

Key Takeaways

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

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

The fast pointer moves two steps to eventually meet the slow pointer inside the loop if one exists.

Proper pointer checks prevent runtime errors during detection.

Detecting loops is essential to avoid infinite loops and ensure safe linked list operations.

Practice

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

easy

A. The linked list has only one node

B. The linked list has no nodes

C. The linked list nodes are sorted in ascending order

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

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 D

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 list
• Confusing empty list with circular list
• Assuming single node list is always circular

2. Which of the following is the correct way to check if a linked list is circular in JavaScript?

easy

A. Count nodes and compare with array length

B. Use two pointers moving at different speeds and check if they meet

C. Check if head is null only

D. Sort the linked list nodes

Solution

1. Step 1: Understand Floyd's cycle detection

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

2. Step 2: Eliminate wrong options

   Checking head null only doesn't detect loops. Counting nodes or sorting is unrelated.

3. Final Answer:

   Use two pointers moving at different speeds and check if they meet -> Option B

4. Quick Check:

   Two-pointer cycle detection = correct method [OK]

Hint: Two pointers meeting means circular list [OK]

Common Mistakes:

• Only checking if head is null
• Trying to sort linked list to detect cycle
• Counting nodes without loop detection

3. What will be the output of the following code snippet?

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

const head = new Node(1);
const second = new Node(2);
const third = new Node(3);
head.next = second;
second.next = third;
third.next = second; // creates a loop

function isCircular(head) {
  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. false

B. undefined

C. true

D. TypeError

Solution

1. Step 1: Analyze linked list structure

   Nodes 1 -> 2 -> 3, and third node points back to second, creating a loop.

2. Step 2: Trace two-pointer loop detection

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

3. Final Answer:

   true -> Option C

4. Quick Check:

   Loop detected = true [OK]

Hint: Loop causes pointers to meet, returning true [OK]

Common Mistakes:

• Assuming no loop because list looks linear
• Confusing pointer equality check
• Expecting false without tracing pointers

4. Find the error in this code that tries to detect a circular linked list:

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

medium

A. The while condition should check if fast and fast.next exist

B. The comparison should use === instead of ==

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

D. The function should return false inside the loop

Solution

1. Step 1: Check while loop condition safety

   fast.next.next is accessed without confirming fast is not null, can cause error if fast is null.

2. Step 2: Correct condition to avoid runtime error

   Condition should be while (fast && fast.next) to safely access fast.next.next.

3. Final Answer:

   The while condition should check if fast and fast.next exist -> Option A

4. Quick Check:

   Check fast and fast.next before accessing next nodes [OK]

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

Common Mistakes:

• Not checking if fast is null before accessing fast.next.next
• Using == instead of === (not critical here)
• Moving slow pointer two steps incorrectly

5. Given a linked list where the last node points back to the head, how can you modify the detection function to also return the node where the loop starts?

function detectLoopStart(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      // Loop detected
      slow = head;
      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow;
    }
  }
  return null;
}

hard

A. The function returns the node where the loop starts by resetting slow to head and moving both pointers one step

B. The function returns true if a loop exists but does not find the start node

C. The function incorrectly moves fast pointer one step after detection

D. The function will always return null because slow and fast never meet

Solution

1. Step 1: Detect loop using two pointers

   Slow and fast pointers meet inside the loop confirming a cycle.

2. Step 2: Find loop start node

   Reset slow to head, move slow and fast one step at a time until they meet again; this node is loop start.

3. Final Answer:

   The function returns the node where the loop starts by resetting slow to head and moving both pointers one step -> Option A

4. Quick Check:

   Reset slow and move both pointers to find loop start [OK]

Hint: Reset slow to head after detection to find loop start [OK]

Common Mistakes:

• Returning true instead of loop start node
• Moving fast pointer incorrectly after detection
• Assuming slow and fast never meet