Detect if a Linked List is Circular in DSA Typescript - Execution Trace

Concept Flow - Detect if a Linked List is Circular

Start at head

↓

Initialize slow and fast pointers

↓

Move slow by 1 step

↓

Move fast by 2 steps

↓

Check if slow == fast?

Yes→List is Circular

No↓

Check if fast or fast.next is null?

Yes→List is NOT Circular

↩Back to Move slow and fast pointers

Start with two pointers moving at different speeds; if they meet, the list is circular; if fast pointer reaches end, it's not.

Execution Sample

DSA Typescript

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

This code uses two pointers moving at different speeds to detect if the linked list loops back on itself.

Execution Table

Step	Operation	Slow Pointer Node	Fast Pointer Node	Pointer Changes	Visual State
1	Initialize slow and fast to head	Node 1	Node 1	slow=head, fast=head	1 -> 2 -> 3 -> 4 -> 5 -> null
2	Move slow by 1, fast by 2	Node 2	Node 3	slow=2, fast=3	1 -> 2 -> 3 -> 4 -> 5 -> null
3	Move slow by 1, fast by 2	Node 3	Node 5	slow=3, fast=5	1 -> 2 -> 3 -> 4 -> 5 -> null
4	while condition check fails (fast.next is null)	Node 3	Node 5	No pointer change	1 -> 2 -> 3 -> 4 -> 5 -> null
5	fast or fast.next is null, exit loop	Node 3	Node 5	No pointer change	1 -> 2 -> 3 -> 4 -> 5 -> null
6	Return false - list is not circular	-	-	-	List is linear, no cycle detected

💡 Loop exited because fast.next is null, so list is not circular

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
slow	Node 1	Node 2	Node 3	Node 3	Node 3
fast	Node 1	Node 3	Node 5	Node 5	Node 5

Key Moments - 3 Insights

Why do we move fast pointer by two steps and slow pointer by one?

Moving fast pointer twice as fast ensures that if there is a cycle, fast will eventually catch slow inside the loop, as shown in steps 2-4 of the execution_table.

What if the list is empty or has only one node?

If head is null or head.next is null, fast or fast.next will be null immediately, so the loop exits and returns false, meaning no cycle, as shown in step 5.

Why do we check if slow === fast inside the loop?

If slow and fast point to the same node, it means fast caught slow inside a cycle, so the list is circular. This check is done each iteration before continuing, as in step 3 if it were circular.

Visual Quiz - 3 Questions

Look at the execution_table, what node is the slow pointer at after step 3?

A Node 3

B Node 5

C Node 2

D Node 4

💡 Hint

Check the 'Slow Pointer Node' column at step 3 in the execution_table.

At which step does the loop condition fail (fast or fast.next is null), causing the loop to exit?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Operation' column in step 4.

If the linked list had a cycle, what would happen in the execution_table?

A slow and fast pointers would never meet

B slow and fast pointers would meet at some node

C fast pointer would become null

D slow pointer would become null

💡 Hint

Refer to the 'Operation' and 'Pointer Changes' columns where slow === fast means circular.

Concept Snapshot

Detect Circular Linked List:
- Use two pointers: slow (1 step), fast (2 steps)
- Move pointers until fast or fast.next is null (no cycle)
- If slow == fast at any point, list is circular
- Return true if cycle found, else false

Full Transcript

To detect if a linked list is circular, we use two pointers starting at the head. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. If the list has a cycle, the fast pointer will eventually meet the slow pointer inside the loop. If the fast pointer reaches the end (null), the list is not circular. This method efficiently detects cycles without extra memory.

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