Find Middle Element of Linked List in DSA Typescript - Execution Trace

Concept Flow - Find Middle Element of Linked List

Start: head points to first node

↓

Initialize two pointers: slow and fast at head

↓

Loop: fast and fast.next not null?

No→Stop

Yes↓

Move slow by one node

↓

Move fast by two nodes

↓

Repeat loop

↓

When loop ends, slow points to middle node

↓

Return slow.data as middle element

Use two pointers moving at different speeds to find the middle node in one pass.

Execution Sample

DSA Typescript

class Node {
  data: number;
  next: Node | null;
  constructor(data: number) {
    this.data = data;
    this.next = null;
  }
}

function findMiddle(head: Node | null): number | null {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow ? slow.data : null;
}

Finds the middle element of a singly linked list using slow and fast pointers.

Execution Table

Step	Operation	slow Pointer Node	fast Pointer Node	Visual State
1	Initialize slow and fast at head	Node(data: 10)	Node(data: 10)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ → │ data:20│ → │ data:30│ → │ data:40│ → │ data:50│ ∅ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head = slow = fast
2	Check fast and fast.next (fast=10, fast.next=20) - continue	Node(data: 20)	Node(data: 30)	Step 2: slow moves to 20, fast moves to 30 ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ → │ data:20│ → │ data:30│ → │ data:40│ → │ data:50│ ∅ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head slow fast
3	Check fast and fast.next (fast=30, fast.next=40) - continue	Node(data: 30)	Node(data: 50)	Step 3: slow moves to 30, fast moves to 50 ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ → │ data:20│ → │ data:30│ → │ data:40│ → │ data:50│ ∅ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head slow fast
4	Check fast and fast.next (fast=50, fast.next=null) - stop	Node(data: 30)	Node(data: 50)	Loop ends because fast.next is null Middle node is 30
5	Return slow.data as middle element	Node(data: 30)	Node(data: 50)	Middle element found: 30

💡 fast.next is null at step 4, loop stops, slow points to middle node

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4 (final)
slow	Node(10)	Node(20)	Node(30)	Node(30)
fast	Node(10)	Node(30)	Node(50)	Node(50)

Key Moments - 3 Insights

Why does the loop stop when fast.next is null, not when fast is null?

Because fast moves two steps at a time, checking fast.next ensures we don't access null.next which would cause an error. See execution_table step 4 where fast=Node(50) and fast.next=null stops the loop.

Why does slow pointer point to the middle node when the loop ends?

Slow moves one step each iteration while fast moves two. When fast reaches the end, slow is halfway through the list. See execution_table steps 2-4 where slow moves 10→20→30 while fast moves 10→30→50.

What if the list has even number of nodes? Which node is returned as middle?

The slow pointer will point to the second middle node in an even-length list because fast will become null after passing the last node. This is consistent with the loop condition. (Not shown here but same logic applies.)

Visual Quiz - 3 Questions

Look at the execution_table, what node does the slow pointer point to after step 3?

A Node with data 40

B Node with data 20

C Node with data 30

D Node with data 50

💡 Hint

Check the 'slow Pointer Node' column in execution_table row for step 3

At which step does the loop stop because fast.next is null?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the 'Operation' and 'fast Pointer Node' columns in execution_table for loop termination

If the linked list had one more node with data 60, where would slow point at loop end?

A Node with data 30

B Node with data 40

C Node with data 50

D Node with data 60

💡 Hint

Think about slow moving one step and fast moving two steps; slow will be at the second middle node in even length lists

Concept Snapshot

Find Middle Element of Linked List:
- Use two pointers: slow and fast starting at head
- Move slow by 1 node, fast by 2 nodes each loop
- Loop ends when fast or fast.next is null
- Slow pointer then points to middle node
- Returns slow.data as middle element

Full Transcript

To find the middle element of a linked list, we use two pointers called slow and fast. Both start at the head of the list. In each step, slow moves one node forward, while fast moves two nodes forward. We keep doing this until fast reaches the end of the list or has no next node. At that point, slow will be pointing to the middle node. We then return the data of the slow node as the middle element. This method works in one pass and is efficient. The execution table shows how slow and fast pointers move through the list step by step, and the variable tracker records their positions after each step.

Practice

1. What is the main idea behind finding the middle element of a singly linked list using the two-pointer technique?

easy

A. Use two pointers, one moving twice as fast as the other; when the fast pointer reaches the end, the slow pointer is at the middle.

B. Count all nodes first, then traverse again to the middle index.

C. Reverse the linked list and pick the middle node from the reversed list.

D. Use a stack to store all nodes and pop half of them to find the middle.

Solution

1. Step 1: Understand the two-pointer technique

   One pointer moves one step at a time (slow), the other moves two steps at a time (fast).

2. Step 2: Identify the middle when fast pointer reaches the end

   When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

3. Final Answer:

   Use two pointers, one moving twice as fast as the other; when the fast pointer reaches the end, the slow pointer is at the middle. -> Option A

4. Quick Check:

   Two-pointer technique = slow at middle when fast ends [OK]

Hint: Move one pointer twice as fast to find middle easily [OK]

Common Mistakes:

• Trying to count nodes first wastes extra time
• Reversing list is unnecessary and inefficient
• Using extra space like stack is not optimal

2. Which of the following TypeScript code snippets correctly initializes a singly linked list node?

easy

A. class Node { value: number; next: any; constructor(value: number) { this.value = value; this.next = undefined; } }

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

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

D. class Node { value: number; next: Node | null; constructor(value: number) { this.value = value; this.next = null; } }

Solution

1. Step 1: Check the type of the next pointer

   It should be either another Node or null if it is the last node.

2. Step 2: Verify constructor initialization

   The constructor sets value and initializes next to null correctly.

3. Final Answer:

   class Node { value: number; next: Node | null; constructor(value: number) { this.value = value; this.next = null; } } -> Option D

4. Quick Check:

   Next pointer type includes null and initialized to null [OK]

Hint: Next pointer must allow null for list end [OK]

Common Mistakes:

• Not allowing next to be null causes type errors
• Initializing next to undefined instead of null
• Using any type loses type safety

3. What will be the output of the following TypeScript code that finds the middle element of a linked list?

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

function findMiddle(head: Node | null): number | null {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow ? slow.value : null;
}

// Create linked list: 10 -> 20 -> 30 -> 40 -> 50
const head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
head.next.next.next.next = new Node(50);

console.log(findMiddle(head));

medium

A. 20

B. 30

C. 40

D. 50

Solution

1. Step 1: Trace slow and fast pointers through the list

   Initially both at 10. After first loop: slow=20, fast=30; second loop: slow=30, fast=50; third loop ends as fast.next is null.

2. Step 2: Identify slow pointer value at loop end

   Slow pointer is at node with value 30, which is the middle.

3. Final Answer:

   30 -> Option B

4. Quick Check:

   Slow pointer stops at middle node value 30 [OK]

Hint: Fast pointer moves twice, slow pointer lands on middle [OK]

Common Mistakes:

• Returning fast pointer value instead of slow
• Not checking fast.next in while condition
• Off-by-one errors in pointer movement

4. Identify the error in the following TypeScript function that attempts to find the middle element of a linked list:

function findMiddle(head: Node | null): number | null {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow.value;
}

medium

A. The fast pointer should move one step at a time, not two.

B. The while loop condition should be while (fast !== null) only.

C. The function does not check if slow is null before accessing slow.value.

D. The function should return fast.value instead of slow.value.

Solution

1. Step 1: Analyze pointer null safety before accessing value

   Slow pointer can be null if the list is empty, so accessing slow.value without check can cause runtime error.

2. Step 2: Identify missing null check before return

   The function should check if slow is not null before returning slow.value to avoid errors.

3. Final Answer:

   The function does not check if slow is null before accessing slow.value. -> Option C

4. Quick Check:

   Always check pointer is not null before accessing properties [OK]

Hint: Check for null before accessing node properties [OK]

Common Mistakes:

• Ignoring null checks causes runtime errors
• Changing fast pointer movement breaks logic
• Returning fast.value misses middle element

5. Given a singly linked list with an even number of nodes, how can you modify the two-pointer approach to return the first middle element instead of the second middle element?

hard

A. Initialize fast pointer to head.next instead of head and then proceed normally.

B. Move slow pointer two steps and fast pointer one step in each iteration.

C. Use a stack to store nodes and pop half to get the second middle.

D. Traverse the list twice: first to count nodes, second to middle+1 node.

Solution

1. Step 1: Understand difference between first and second middle in even-length list

   For even nodes, two middle nodes exist; the second middle is the one after the first middle.

2. Step 2: Modify fast pointer start to head.next

   Starting fast pointer at head.next shifts slow pointer to first middle when fast reaches end.

3. Final Answer:

   Initialize fast pointer to head.next instead of head and then proceed normally. -> Option A

4. Quick Check:

   Fast starts at second node to get first middle [OK]

Hint: Start fast pointer one step ahead for first middle [OK]

Common Mistakes:

• Swapping slow and fast pointer steps breaks logic
• Using stack wastes extra space
• Counting nodes twice is inefficient