#876
Middle of the Linked List
Easy Fast & slow pointers
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the middle node of a linked list; for an even number of nodes, return the second of the two middle nodes.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the middle node (second middle for even length).
Why this works: fast moves 2 steps while slow moves 1; when fast reaches the end, slow is halfway.
Example: 1 → 2 → 3 → 4 → 5
slow 1, fast 1 → slow 2, fast 3 → slow 3, fast 5 → stopmiddle 3
✦Hints open one at a time
Move one pointer one step and another two steps at a time.
When the fast one reaches the end, the slow one is in the middle.
↗Approach
slow = fast = head; while fast and fast.next exist, advance slow by one and fast by two. Return slow.
</>Solution (Java)
/**
* class ListNode { int val; ListNode next; } // provided by LeetCode
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}!Common mistake
Using the loop condition fast.next.next != null, which returns the first middle for even lengths.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Linked List
🎬 Episodes 40–45: video coming soon