Middle of the Linked List
Problem Statement
Given the head of a singly linked list, return the middle node. If the list has two middle nodes, return the second middle node.
Input
The head pointer of a non-empty singly linked list.
Output
The node that represents the middle of the list; for even length, return the second middle.
Constraints
- •
1 <= number of nodes <= 100 - •
1 <= Node.val <= 100
Examples
Example 1
head = **1 -> 2 -> 3 -> 4 -> 5 -> null**
Node with value **3**Example 2
head = **1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null**
Node with value **4**Learning Objectives
- Recognise when a fast pointer moving twice as quickly can locate a midpoint in one pass.
- Explain why the standard loop condition returns the second middle for even-length lists.
- Avoid dereferencing **fast.next** before proving it exists.
- Connect middle finding to cycle detection, palindrome checks, and split-list problems.
Intuition
Pattern Recognition
The signal is a question about the middle, half, or split point of a linked list when you do not have array indexing. A single pass with a counter works, but it usually needs either two passes or stored length. The linked-list pattern is fast and slow pointers: move slow one node at a time and fast two nodes at a time.
The pointer trap is the loop guard. You must only read fast.next.next after confirming fast and fast.next are not null. With the condition fast != null && fast.next != null, slow advances once for every two steps of fast. On even length, fast falls off the list exactly after slow steps onto the second middle.
Common mistakes
- ×Using **while fast.next != null** and accidentally returning the first middle or throwing on short lists.
- ×Moving **fast** two steps without checking both **fast** and **fast.next**.
- ×Counting nodes in one pass and then forgetting the problem asks for the second middle on even length.
- ×Returning **fast** instead of **slow**, even though **fast** is only the pace-setting pointer.
Algorithm Explanation
Key idea
Use relative speed instead of length. slow moves one edge per loop, fast moves two edges per loop. When fast reaches the end, slow has taken half as many steps and therefore sits at the middle. The standard guard naturally returns the second middle for even length.
Pointer walkthrough
For 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null, start both pointers at 1. After one loop, slow = 2 and fast = 3. After two loops, slow = 3 and fast = 5. The guard still allows one more loop because fast.next is 6. After the third loop, slow = 4 and fast = null. The traversal stops and 4 is returned, which is the second middle.
For odd length 1 -> 2 -> 3 -> 4 -> 5 -> null, the same loop stops when fast = 5 because fast.next is null. At that moment slow = 3, the single middle.
Algorithm
- Set both slow and fast to head.
- While fast is not null and fast.next is not null, advance slow by one node.
- In the same loop, advance fast by two nodes.
- When the loop stops, return slow.
Solutions
Solution: Fast and slow pointers
Move fast twice as quickly as slow. The distance covered by fast proves that slow has crossed exactly half the list when the traversal ends.
Step-by-step
- Place slow and fast at head.
- Continue while fast and fast.next both exist.
- Move slow to slow.next.
- Move fast to fast.next.next.
- Return slow, which is the middle node under the second-middle convention.
O(n)
O(1)
The list is scanned once and only two pointers are stored.
Java implementation
Dry Run
Sample input
head = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null. The expected answer is the second middle, node 4.
| iteration | slow before | fast before | slow after | fast after |
|---|---|---|---|---|
| start | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 2 | 3 |
| 2 | 2 | 3 | 3 | 5 |
| 3 | 3 | 5 | 4 | null |
The loop stops because fast is null. slow is at 4, so the algorithm returns the second middle node for the even-length list.
Interview Tips
State the even-length convention before coding. With both pointers starting at head and the guard fast != null && fast.next != null, the method returns the second middle. If an interviewer wanted the first middle, you would adjust the stopping condition or initial fast position.
Likely follow-ups
- How would you return the first middle instead of the second middle?
- How would you split the list into two halves for merge sort?
- How does this template change when detecting a cycle?
- How would you find the node one-third of the way through a linked list?
Similar Problems
Key Takeaways
- Fast and slow pointers replace random access when a linked-list midpoint is needed.
- The guard **fast != null && fast.next != null** is both a safety check and a convention choice.
- For even length, this setup returns the second middle node.
- Middle-finding is a setup step for split, palindrome, and merge-sort problems.