Find Middle Element of Linked List in DSA Typescript

Mental Model

To find the middle, use two pointers moving at different speeds so when the fast one reaches the end, the slow one is in the middle.

Analogy: Imagine walking on a path with a friend. You walk one step at a time, your friend runs two steps at a time. When your friend finishes the path, you are halfway through.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow ↑
fast ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5 -> null

Goal: Find the middle element of the linked list

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

head -> [slow->1, fast->1] -> 2 -> 3 -> 4 -> 5 -> null

Why: Both pointers start at the beginning to start traversal

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

head -> 1 -> [slow->2] -> [fast->3] -> 4 -> 5 -> null

Why: Fast moves twice as fast to reach the end quicker

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

head -> 1 -> 2 -> [slow->3] -> 4 -> [fast->5] -> null

Why: Continue moving pointers until fast reaches the end

Step 4: Fast cannot move 2 steps further (end reached), stop

head -> 1 -> 2 -> [slow->3] -> 4 -> 5 -> null

Why: Slow pointer is now at the middle node

Result:

head -> 1 -> 2 -> [3] -> 4 -> 5 -> null
Middle element is 3

Annotated Code

DSA Typescript

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

function findMiddle(head: ListNode | null): number | null {
  if (!head) return null; // empty list
  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
  }

  return slow ? slow.value : null;
}

// Driver code
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

const middle = findMiddle(head);
console.log(middle !== null ? middle.toString() : "List is empty");

if (!head) return null; // empty list

handle empty list edge case

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

loop until fast reaches end or one before end

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

return slow ? slow.value : null;

return value at slow pointer which is middle

Output

3

Complexity Analysis

Time: O(n) because we traverse the list once with two pointers

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

vs Alternative: Compared to counting nodes first then traversing again to middle (O(2n)), this method is faster and uses less code

Edge Cases

empty list

returns null indicating no middle element

DSA Typescript

if (!head) return null; // empty list

list with one element

returns the single element as middle

DSA Typescript

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

list with even number of elements

returns the second middle element (e.g., for 4 nodes, returns node 3)

DSA Typescript

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

When to Use This Pattern

When asked to find the middle of a linked list efficiently, use the slow and fast pointer technique because it finds the middle in one pass without extra space.

Common Mistakes

Mistake: Moving both pointers by one step each time and then trying to find middle
Fix: Move fast pointer by two steps and slow pointer by one step to find middle in one pass

Mistake: Not checking if fast or fast.next is null before moving fast pointer
Fix: Add condition in while loop: fast !== null && fast.next !== null

Summary

Finds the middle element of a linked list using two pointers moving at different speeds.

Use when you need the middle node quickly without counting all nodes first.

The fast pointer moves twice as fast as the slow pointer, so when fast reaches the end, slow is in the middle.

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