876. Middle of the Linked List (Easy)

Problem

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.

Example

• head = [1,2,3,4,5] → node 3 (middle of 5 nodes)
• head = [1,2,3,4,5,6] → node 4 (second of the two middle nodes)

LeetCode 876 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, two passes

First pass: count nodes. Second pass: walk to the middle index.

Python

def middle_node(head):
    n, cur = 0, head
    while cur:                         # L1: O(n) count
        n += 1
        cur = cur.next
    cur = head
    for _ in range(n // 2):           # L2: O(n/2) walk to middle
        cur = cur.next
    return cur

TypeScript

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

function middleNode(head: ListNode | null): ListNode | null {
    let n = 0, cur = head;
    while (cur) { n++; cur = cur.next; }  // L1: O(n) count
    cur = head;
    for (let i = 0; i < Math.floor(n / 2); i++) cur = cur!.next;  // L2: O(n/2) walk
    return cur;
}

Swift

final class Solution {
func middleNode(_ head: ListNode?) -> ListNode? {
        var count = 0
        var current = head
        while current != nil {
            count += 1
            current = current?.next
        }
        current = head
        for _ in 0..<(count / 2) {
            current = current?.next
        }
        return current
    }
}

Where the time goes, line by line

Variables: n = number of nodes.

Line	Per-call cost	Times executed	Contribution
L1 (count pass)	$O(1)$	n	$O(n)$
L2 (walk to middle)	$O(1)$	n/2	$O(n)$

Complexity

• Time: $O(n)$, two passes
• Space: $O(1)$

Correct but walks the list twice.

Approach 2: Slow and fast pointers (optimal)

slow advances one step per iteration; fast advances two. When fast reaches the end of the list, slow is at the middle. For even-length lists, fast runs off the end after the second-to-last node, leaving slow at the second middle (which is what the problem requires).

Python

def middle_node(head):
    slow = fast = head
    while fast and fast.next:          # L1: fast needs current and next node
        slow = slow.next              # L2: O(1) advance slow by 1
        fast = fast.next.next         # L3: O(1) advance fast by 2
    return slow                        # L4: slow is at the middle

TypeScript

function middleNode(head: ListNode | null): ListNode | null {
    let slow = head, fast = head;
    while (fast && fast.next) {        // L1: fast needs current and next node
        slow = slow!.next;            // L2: O(1) advance slow by 1
        fast = fast.next.next;        // L3: O(1) advance fast by 2
    }
    return slow;                       // L4: slow is at the middle
}

Swift

final class Solution {
func middleNode(_ head: ListNode?) -> ListNode? {
        var slow = head
        var fast = head
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        return slow
    }
}

Where the time goes, line by line

Variables: n = number of nodes.

Line	Per-call cost	Times executed	Contribution
L1 (loop guard)	$O(1)$	n/2	$O(n)$
L2/L3 (advance pointers)	$O(1)$	n/2	$O(n)$ ← dominates
L4 (return)	$O(1)$	1	$O(1)$

The loop runs exactly floor(n/2) times (for odd n) or n/2 times (for even n). One pass, constant space.

Complexity

• Time: $O(n)$, driven by L2/L3 (one pass with two pointers).
• Space: $O(1)$.

Step-by-step trace

[1, 2, 3, 4, 5]  (odd, n=5)

Start:   slow=1, fast=1
Step 1:  slow=2, fast=3
Step 2:  slow=3, fast=5
fast.next is None -> exit
Return slow = node(3)  correct: middle of 5

[1, 2, 3, 4, 5, 6]  (even, n=6)

Start:   slow=1, fast=1
Step 1:  slow=2, fast=3
Step 2:  slow=3, fast=5
Step 3:  slow=4, fast=None (fast.next.next)
fast is None -> exit
Return slow = node(4)  correct: second middle of 6

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Key takeaways

• The 2:1 speed ratio means slow travels half the distance fast travels. When fast hits the end, slow is at the midpoint.
• The loop condition fast and fast.next guards against two scenarios: fast is None (even-length list just exhausted) and fast.next is None (odd-length list at last node, about to overrun).
• This pattern is the first half of Reorder List (143), which finds the middle, reverses the second half, and interleaves.

Test cases

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

def from_list(vals):
    dummy = ListNode()
    cur = dummy
    for v in vals:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next

def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def _run_tests():
    # Odd length: middle is the true center
    assert middle_node(from_list([1, 2, 3, 4, 5])).val == 3
    # Even length: second middle
    assert middle_node(from_list([1, 2, 3, 4, 5, 6])).val == 4
    # Two nodes: second node is the middle
    assert middle_node(from_list([1, 2])).val == 2
    # Single node
    assert middle_node(from_list([1])).val == 1
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

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

function fromList(vals: number[]): ListNode | null {
    const dummy = new ListNode();
    let cur = dummy;
    for (const v of vals) { cur.next = new ListNode(v); cur = cur.next; }
    return dummy.next;
}

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;
}

console.assert(middleNode(fromList([1, 2, 3, 4, 5]))!.val === 3);
console.assert(middleNode(fromList([1, 2, 3, 4, 5, 6]))!.val === 4);
console.assert(middleNode(fromList([1, 2]))!.val === 2);
console.assert(middleNode(fromList([1]))!.val === 1);
console.log("all tests pass");

Related topics

• 141. Linked List Cycle, Floyd’s slow/fast pointer for cycle detection
• 143. Reorder List, uses middle-finding as its first step
• 206. Reverse Linked List, pointer fundamentals

Related concepts

• Fast and Slow Pointers, the pointer speed trick for finding middles, cycles, and distance from the end.
• Linked List Pointer Rewiring, the link editing pattern for changing node order without losing the chain.