Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Fast & Slow Pointers

Guide 6 of 6 · Path 6 of 6

← PreviousNext pattern: Binary Search →

Interactive

Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 8
1
2
3
4
5

Slow steps +1, fast steps +2. No need to know the list length.

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Easyfast-slow-pointers

Middle of the Linked List

Problem (restated)

Given the head of a singly linked list, return the middle node. If two middles, return the second.

Intuition

Slow moves one step, fast two; when fast finishes, slow is at the middle.

Approaches

Fast & slow pointers

Tested only
Time O(n)Space O(1)

Idea. Advance until fast is null or fast.next is null; return slow.

Walkthrough. 1→2→3→4→5 → slow ends on 3; even length ends on second middle.

Trade-offs. Counting length first is two passes; this is one pass O(1) space.

Solution
export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}
export function middleNode(head: ListNode | null): ListNode | null {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}
export function middleNode(head: ListNode | null): ListNode | null {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow;
}

Reflection