Middle Node

Tags

Middle Node

Category

Linked Lists

Difficulty

Easy

Problem Statement

Given the head of a singly linked list, return the middle node. If there are two middle nodes (even-length list), return the second middle node.

Intuition

The classic technique is the slow-and-fast pointer approach. A slow pointer advances one step at a time while a fast pointer advances two steps. When the fast pointer reaches the end, the slow pointer is at the middle. This works because the slow pointer covers exactly half the distance of the fast pointer.

Approach

  1. Initialize both slow and fast pointers to the head.
  2. While fast is not null and fast.next is not null:
    • Move slow one step forward.
    • Move fast two steps forward.
  3. When the loop ends, slow points to the middle node. Return it.

Pseudocode

function middleNode(head):
    slow = head
    fast = head
    while fast is not null and fast.next is not null:
        slow = slow.next
        fast = fast.next.next
    return slow

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. The fast pointer traverses the entire list once.
  • Space: O(1) — only two pointers are used.

Key Insights

  • The slow/fast pointer technique is a fundamental linked list pattern used in many problems (cycle detection, finding the start of a cycle, etc.).
  • For an even-length list, this approach naturally returns the second middle node because the fast pointer checks fast.next before stopping.
  • An alternative approach is to count all nodes first, then traverse to the n/2-th node, but this requires two passes.

Edge Cases

  • Single-node list: the head itself is the middle node.
  • Two-node list: the second node is returned (the second middle).
  • Odd-length list: the exact middle is returned.
  • Even-length list: the second of the two middle nodes is returned.

Linked mentions