Find the Middle Node of a Linked List
Solve this Problem
Given the
head of a singly linked list, return the middle node. If the list has two middle nodes (an even count), return the second one.
Since a linked list has no length property, finding "the middle" naively means counting first. The optimal solution avoids that entirely with a fast and slow pointerFast & Slow PointersTwo pointers start together but move at different speeds — typically one step vs. two steps per iteration. Because the faster one covers exactly double the distance, its position relative to the end tells you something useful about the slower one's position — here, that it's sitting on the middle. — by the time fast has covered the whole list, slow has covered exactly half of it.
Test Case 1:
Input:head = [1, 2, 3, 4, 5]
Output:[3, 4, 5]
Explanation:Odd length — the true middle is 3, and the returned list starts there.
Test Case 2:
Input:head = [1, 2, 3, 4, 5, 6]
Output:[4, 5, 6]
Explanation:Even length — there are two middles (3 and 4); the second one (4) is returned.
Test Case 3:
Input:head = [1]
Output:[1]
Explanation:A single node is its own middle.
Constraints
- ◆
1 ≤ number of nodes in head ≤ 10⁴ - ◆
-10⁹ ≤ node value ≤ 10⁹ - ◆
For an even-length list, return the second of the two middle nodes
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public Node middleNode(Node head) { |
| 3 | Node slow = head, fast = head; |
| 4 | while (fast != null && fast.next != null) { |
| 5 | slow = slow.next; |
| 6 | fast = fast.next.next; |
| 7 | } |
| 8 | return slow; |
| 9 | } |
| 10 | } |
| 11 |
1
slowfast
2
3
4
5
Variables
slow
1fast
1INITIALIZE
Both slow and fast start at head.
Step 1 / 4
Approach & Solutions
Brute Force — Count Nodes, Then Traverse to n/2
GoodWalk the list once just to count its length n. Then walk it again from head, stopping after n / 2 steps — that's the middle node (integer division naturally lands on the second middle for even n). Correct, but it requires knowing the length before the real traversal can even begin.
Time
O(n)Space
O(1)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node middleNode(Node head) {
9 int count = 0;
10 Node curr = head;
11 while (curr != null) {
12 count++;
13 curr = curr.next;
14 }
15 curr = head;
16 for (int i = 0; i < count / 2; i++) {
17 curr = curr.next;
18 }
19 return curr;
20 }
21}Optimal — Slow & Fast Pointers, Single Pass
OptimalMove slow one step and fast two steps at a time, both starting at head. Since fast always covers exactly twice the distance slow does, the moment fast runs out of list, slow has covered exactly half that distance — landing it on the middle node, in a single pass.
Time
O(n)Space
O(1)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node middleNode(Node head) {
9 Node slow = head, fast = head;
10 while (fast != null && fast.next != null) {
11 slow = slow.next;
12 fast = fast.next.next;
13 }
14 return slow;
15 }
16}