Detect if a Linked List is Circular in DSA Typescript

Mental Model

We want to check if the list loops back to an earlier node instead of ending.

Analogy: Imagine walking down a path that either ends or loops back to where you started, like a circular track.

1 -> 2 -> 3 -> 4 -> null

or

1 -> 2 -> 3 -> 4 ->
          ↑       ↓
          ←-------

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> points back to node 2 (circular)

Goal: Detect if the list has a loop (circular) or ends normally

Step 1: start slow and fast pointers at head (node 1)

[slow->1] -> [fast->1] -> 2 -> 3 -> 4 -> points back to 2

Why: We need two pointers to detect a loop by moving at different speeds

Step 2: move slow by 1 step to node 2, fast by 2 steps to node 3

1 -> [slow->2] -> [fast->3] -> 4 -> points back to 2

Why: Fast pointer moves twice as fast to catch slow if loop exists

Step 3: move slow by 1 step to node 3, fast by 2 steps to node 2 (loop back)

1 -> 2 -> [slow->3] -> 4 -> [fast->2] -> points back to 2

Why: Fast pointer loops back, slow moves forward, they get closer

Step 4: move slow by 1 step to node 4, fast by 2 steps to node 4

1 -> 2 -> 3 -> [slow->4] -> [fast->4] -> points back to 2

Why: Both pointers meet at node 4, confirming a loop

Result:

1 -> 2 -> 3 -> 4 -> points back to 2 (circular) -> loop detected: true

Annotated Code

DSA Typescript

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

function isCircular(head: ListNode | null): boolean {
  if (!head) return false; // empty list can't be circular
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next; // move slow by 1
    fast = fast.next.next; // move fast by 2
    if (slow === fast) {
      return true; // pointers met, loop detected
    }
  }
  return false; // fast reached end, no loop
}

// Driver code to create circular list: 1->2->3->4->2...
const node4 = new ListNode(4);
const node3 = new ListNode(3, node4);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);
node4.next = node2; // create loop back to node2

console.log(isCircular(node1));

if (!head) return false; // empty list can't be circular

handle empty list edge case

while (fast !== null && fast.next !== null) {

continue loop while fast pointer can move ahead

slow = slow!.next; // move slow by 1

advance slow pointer by one node

fast = fast.next.next; // move fast by 2

advance fast pointer by two nodes

if (slow === fast) {

check if pointers meet indicating a loop

return true; // pointers met, loop detected

loop found, return true

return false; // fast reached end, no loop

no loop found, return false

Output

true

Complexity Analysis

Time: O(n) because both pointers traverse the list at most once until they meet or reach the end

Space: O(1) because only two pointers are used regardless of list size

vs Alternative: Compared to using a hash set to track visited nodes (O(n) space), this uses constant space making it more efficient

Edge Cases

empty list (head is null)

returns false immediately because no nodes exist

DSA Typescript

if (!head) return false; // empty list can't be circular

single node pointing to itself

detects loop because slow and fast meet at the single node

DSA Typescript

if (slow === fast) { return true; }

list with no loop (ends with null)

fast pointer reaches null and function returns false

DSA Typescript

while (fast !== null && fast.next !== null)

When to Use This Pattern

When you see a problem asking if a linked list loops back to an earlier node, use the two-pointer (slow and fast) technique to detect cycles efficiently.

Common Mistakes

Mistake: Checking only if slow equals fast at the start without moving pointers first
Fix: Move slow and fast pointers inside the loop before comparing them

Mistake: Not checking if fast or fast.next is null before moving fast pointer
Fix: Add condition to ensure fast and fast.next are not null before advancing fast pointer

Summary

Detects if a linked list has a cycle by using two pointers moving at different speeds.

Use when you need to know if a linked list loops back on itself instead of ending.

If two pointers moving at different speeds meet, the list is circular.

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