How do you solve Middle of the Linked List?

Initialize two pointers at the head. Move 'slow' one step and 'fast' two steps in each iteration. When 'fast' is null or 'fast.next' is null, 'slow' points to the middle node. Return 'slow'.

Middle of the Linked List

Q: What is the time complexity of Middle of the Linked List?

O(n). Each pointer traverses the list at most once. The 'fast' pointer moves two nodes per iteration, so the loop runs approximately n/2 times.

Q: What pattern does Middle of the Linked List use?

The Pattern: Fast & Slow Pointers (Tortoise and Hare) The Heuristic: Use two pointers moving at different speeds to detect midpoints or cycles in linked structures; the slower pointer's position when the faster pointer reaches the end reveals key structural information.

Easy Fast & Slow Pointers

Problem

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

The number of nodes in the list is in the range [1, 100]
1 ≤ Node.val ≤ 100

Example

Input: head = [1,2,3,4,5]

Output: [3,4,5]

The linked list has 5 nodes. The middle node is the 3rd node with value 3. The algorithm uses two pointers: 'slow' moves one step at a time, 'fast' moves two steps. When 'fast' reaches the end, 'slow' is at the middle. Here, 'slow' points to node with value 3, which is returned.

Approach

Straightforward Solution

A naive approach counts the total number of nodes in one pass, then traverses again to the middle node. This requires two passes and O(n) time.

Core Observation

The middle node is the node at position floor(n/2) + 1 in a 1-indexed list. Using two pointers moving at different speeds allows locating this node in a single pass without knowing the list length upfront.

Path to Optimal

Preview

The key insight is to use two pointers: 'fast' moves twice as fast as 'slow'. When 'fast' reaches the end, 'slow' will be at the middle…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize two pointers at the head. Move 'slow' one step and 'fast' two steps in each iteration…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each pointer traverses the list at most once. The 'fast' pointer moves two nodes per iteration, so the loop runs approximately n/2 times.

Space

O(1)

Only two pointers are used regardless of input size, so the auxiliary space is constant.

Pattern Spotlight

Fast & Slow Pointers (Tortoise and Hare)

Use two pointers moving at different speeds to detect midpoints or cycles in linked structures; the slower pointer's position when the faster pointer reaches the end reveals key structural information.

Solution

Python

1class Solution:
2    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
3
4        slow = head
5        fast = head
6
7        while fast and fast.next:
8            slow = slow.next
9            fast = fast.next.next
10
11        return slow

Step-by-Step Solution

Initialize Slow and Fast Pointers at the Head

4slow = head
5fast = head

Objective

To set up two pointers starting at the head of the linked list to begin traversal.

Key Insight

Starting both pointers at the head ensures they traverse the list in sync, with the fast pointer moving twice as fast. This setup is essential for the two-pointer technique to correctly identify the middle node in one pass.

Interview Quick-Check

Core Logic

Both pointers start at the head to maintain relative positions; the fast pointer's double speed relative to slow is the core mechanism.

State & Boundaries

Initializing both pointers at the head handles edge cases like single-node lists naturally.

Advance Slow by One and Fast by Two Until Fast Reaches End

To traverse the list with two pointers moving at different speeds until the fast pointer reaches the end.

Return the Slow Pointer as the Middle Node

To return the node currently pointed to by the slow pointer, which is the middle node of the list.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 11 Critical

return slow

Return the slow pointer as the middle node.

Returning slow here is the definitive step that solves the problem; it leverages the invariant that slow is at the middle when fast reaches the end, making this line the core of the solution.

Line 7 Critical

while fast and fast.next:

Continue looping while fast and fast.next are not null.

This loop condition is critical to safely advance the fast pointer two steps without causing runtime errors, and it ensures the slow pointer stops exactly at the middle node.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why does moving one pointer twice as fast as the other guarantee that the slower pointer will be at the middle when the faster pointer reaches the end?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Middle of the Linked List from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Middle of the Linked List drill

or drill a free problem

1	`class Solution:`
2	`def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:`
3
4	`slow = head`
5	`fast = head`
6
7	`while fast and fast.next:`
8	`slow = slow.next`
9	`fast = fast.next.next`
10
11	`return slow`