AlgoViz
HomeLinked List

Middle of a LinkedList

Easy

Slow one step, fast two

Problem

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

In simple words

Move a slow pointer one step and a fast pointer two steps; when fast ends, slow sits in the middle.

The idea

Advance one pointer by one node and another by two; when the fast pointer runs off the end, the slow one is at the middle. It finds the middle in a single pass without ever computing the length.

The trick

  • For two middles, the loop condition `fast && fast.next` returns the second.
  • Stopping one step earlier gives the first middle instead.
  • O(n) time, O(1) space, one pass.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
4
5
0
1
2
3
4

Step 1 of 2. Here's the example — head = [1, 2, 3, 4, 5] Values: 1, 2, 3, 4, 5.

1/2
Optimal
timeO(n)spaceO(1)
1slow = head; fast = head2while fast and fast.next:3  slow = slow.next4  fast = fast.next.next5return slow

Input

array
[1, 2, 3, 4, 5]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = 1 -> 2 -> 3 -> 4 -> 5
Output:
3
Explanation:
The exact middle node is 3.

Example 2

Input:
list = 1 -> 2 -> 3 -> 4 -> 5 -> 6
Output:
4
Explanation:
With an even count, take the second middle.

Example 3

Input:
list = 1
Output:
1
Explanation:
One node is its own middle.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.