876. Middle of the Linked List - Detailed Explanation
Problem Statement
Given the head of a singly linked list, return the middle node of the linked list. In a singly linked list, each node points to the next node in sequence. If the list has an even number of nodes (two middle nodes), return the second middle node.
Example 1:
- Input: head = [1, 2, 3, 4, 5]
- Output: [3, 4, 5]
- Explanation: The middle node has value 3, so the list from the middle is [3, 4, 5]. (The returned node is the one with value 3.)
Example 2:
- Input: head = [1, 2, 3, 4, 5, 6]
- Output: [4, 5, 6]
- Explanation: There are two middle nodes (values 3 and 4). The second middle node (value 4) is returned, giving [4, 5, 6].
Example 3:
- Input: head = [1, 2]
- Output: [2]
- Explanation: The list has two nodes. Both 1 and 2 could be considered middle, but we return the second one (value 2).
Constraints:
- The number of nodes,
n, is in the range [1, 100]. (The list is never empty.) 1 <= Node.val <= 100(Node values are positive integers within this range.)- The solution should ideally operate in one pass (linear time) with O(1) additional space.
Hints
- Hint 1: Length Counting. Try traversing the linked list to count the number of nodes. How can knowing the length help you find the middle?
- Hint 2: Use an Index or Array. Consider storing the nodes (or their values) in an array or list. The middle element of that array corresponds to the middle node.
- Hint 3: Two-Pointer Technique. Can you find a way to get the middle in one traversal? Think about using two pointers that move at different speeds (one faster, one slower).
Approaches
There are multiple ways to solve this problem. We will discuss two approaches: a simple two-pass (brute force) method and an optimal one-pass method using fast and slow pointers.
Approach 1: Brute Force (Two-Pass Traversal)
Idea:
The straightforward way is to first determine the length of the linked list, then traverse again to the middle. This approach uses two passes through the list:
- First pass: Count the total number of nodes
nin the list. - Compute middle index: Calculate
midIndex = n // 2(using integer division). Because of how integer division works:- If
nis odd,midIndexwill be the exact middle index (e.g., for n=5, midIndex=2 which is the 3rd node). - If
nis even,midIndexwill ben/2which effectively points to the second middle (e.g., for n=6, midIndex=3 which is the 4th node, the second middle).
- If
- Second pass: Traverse the list again for
midIndexsteps from the head to reach the middle node. - Return that node (or its value as needed).
Step-by-step example (Two-Pass): Suppose the list is [10 -> 20 -> 30 -> 40 -> 50 -> 60] (6 nodes).
- First pass counts
n = 6. - Compute
midIndex = 6 // 2 = 3. - Second pass: Start at head (10) and move 3 steps: after 3 moves, you land on 40. This node (40) is the middle (the second of the two middle nodes in this even-length list).
If the list had an odd number of nodes (say [5 -> 15 -> 25 -> 35 -> 45]), first pass n = 5, midIndex = 5 // 2 = 2. Moving 2 steps from head lands on 25, which is the middle node.
Python Code (Brute Force):
Java Code (Brute Force):
Time Complexity: O(n) – We traverse the list twice (2n steps, which is linear). For example, in a 100-node list, this approach steps through at most 200 nodes in total.
Space Complexity: O(1) – Aside from a few variables, it uses constant extra space. (If an array were used to store nodes, that would be O(n) space, but the two-pass counting method doesn't require extra data structures.)
Approach 2: Optimal Approach (Fast & Slow Pointers)
Idea:
Use two pointers to traverse the list in one pass:
- A slow pointer that moves one step at a time.
- A fast pointer that moves two steps at a time.
When the fast pointer reaches the end of the list, the slow pointer will be at the middle. This works because the fast pointer travels twice as fast, so by the time it covers the whole list, the slow pointer has covered half.
How it works:
- Initialize
slowandfastpointers both at the head of the list. - Move
slowone node forward andfasttwo nodes forward repeatedly in a loop. - Stop when
fastreaches the end of the list (i.e.,fastbecomesnullorfast.nextbecomesnull). At this point,slowwill be at the middle node. - Return the
slowpointer (middle node).
Visual walkthrough (two-pointer method):
-
For an odd-length list,
fastwill becomenullwhileslowis exactly at the middle.
Example: List [1 → 2 → 3 → 4 → 5] (5 nodes)- Start:
slow= 1,fast= 1. - 1st iteration:
slowmoves to 2,fastmoves to 3. - 2nd iteration:
slowmoves to 3,fastmoves to 5. - 3rd iteration:
fastcan move no further (end reached). Stop.slowis at 3, which is the middle node.
- Start:
-
For an even-length list,
fastwill reach the end one step beforeslowdoes, andslowwill end up on the second middle node.
Example: List [1 → 2 → 3 → 4 → 5 → 6] (6 nodes)- Start:
slow= 1,fast= 1. - 1st iteration:
slow→ 2,fast→ 3. - 2nd iteration:
slow→ 3,fast→ 5. - 3rd iteration:
slow→ 4,fasttries to move two steps from 5 and becomesnull(end). Stop.slowis at 4, the second middle node.
- Start:
In both cases, the algorithm correctly finds the middle in a single traversal. This technique is often called the "Tortoise and Hare" algorithm.
Python Code (Fast & Slow Pointers):
Java Code (Fast & Slow Pointers):
Time Complexity: O(n) – We traverse each node at most once (the fast pointer skips ahead, but overall the slow pointer makes ~n/2 moves and the fast pointer ~n moves, which is still linear in total). This is a single-pass solution.
Space Complexity: O(1) – Only a few pointer variables are used, and no extra data structures are needed.
Common Mistakes
- Off-by-One Errors: A frequent bug is miscalculating the middle index or moving the pointers incorrectly by one. For example, using
count/2vs.count//2incorrectly, or moving the slow pointer one time too few or too many in the loop. - Even-Length Handling: Forgetting that even-length lists require returning the second middle. If your two-pointer loop condition or second-pass calculation is off, you might accidentally return the first middle. Always double-check the logic with an even-sized list (like 2 or 6 nodes).
- Null Pointer Exception: In the two-pointer approach, failing to check
fast.nextbefore doingfast = fast.next.nextcan lead to accessingnull.next. Make sure the loop condition iswhile (fast != null && fast.next != null)to safely movefastby two steps. - Returning the Wrong Thing: Remember the problem asks to return the node itself (not just the value). In a test context, returning the node means if you print from that node you get the remaining list. A mistake would be returning the value of the middle node or an index instead of the node reference.
- Not Resetting Pointers: In the two-pass approach, after counting, you must reset your pointer back to head for the second pass. Forgetting to reset (and continuing with a pointer at the end of the list) is an error.
Edge Cases
- Single Node List: If the list has only one node (e.g., [7]), that node is trivially the middle. Both approaches handle this since they would return the head itself.
- Two Node List: For a list like [A, B], both nodes could be considered "middle". By the problem's rule, we return the second node (B). The two-pointer method naturally does this (slow will end at B), and in the counting method
n=2givesmidIndex=1which also returns B. - Even Number of Nodes: Any even-length list will have two central nodes. The expected output is always the later one. Ensure your solution consistently picks the second middle. (Our approaches do this by design.)
- Odd Number of Nodes: Standard case where there is one clear middle. The approaches will return that single middle node.
- Maximum Length (100 nodes): Even though 100 is not very large, our solutions run in linear time O(n) which is efficient. Edge cases here are more about correctness than performance.
- All Nodes Same Value: If all node values are identical (e.g., [1, 1, 1, 1, 1]), the middle is determined by position, not value. Our logic is based on position, so it works regardless of duplicate values.
(Note: The constraints guarantee the list has at least 1 node, so we do not have to handle an "empty list" case in this problem. If we did, we would simply return null or handle it separately.)
Alternative Variations
Variations of the "middle of linked list" problem or related tasks include:
-
First Middle vs Second Middle: In some scenarios, you might be asked to return the first middle node in an even-length list (instead of the second). To do that using the two-pointer method, you can adjust the loop condition slightly (for example, loop while
fast != null && fast.next != nullgives second middle, whereas looping whilefast != null && fast.next.next != nullwould makeslowstop at the first middle). -
Delete the Middle Node: A related problem is to remove the middle node from the list. You can find the middle as we did, then adjust the pointers to skip over it. (LeetCode problem Delete the Middle Node of a Linked List asks for exactly this.)
-
Split the List in Half: In some applications (like Merge Sort on linked lists), you need to split the linked list into two halves from the middle. Once you find the middle, you can use it to break the list into two lists (first half and second half starting from the middle).
-
Middle of Doubly Linked List: If you have a doubly linked list (each node has next and previous pointers), you could technically find the middle by moving two pointers from both ends towards the center. However, the two-pointer (fast/slow) method works just as well on doubly linked lists too.
-
Multiple Passes Constraint: If a variation of the problem explicitly asks you to do it in one pass (single traversal), the two-pointer method is the way to go. Our Approach 2 already satisfies the one-pass requirement.
Related Problems
Here are a few related LeetCode linked list problems and how they connect:
-
LeetCode 19. Remove Nth Node from End of List: Find the n-th node from the end of the list and remove it. This can be solved with a two-pointer technique where one pointer is advanced n steps ahead, then both move until the lead pointer hits the end, so the second pointer lands on the node to remove.
-
LeetCode 234. Palindrome Linked List: Check if a linked list reads the same forward and backward. A common approach is to find the middle of the list (using our middle-finding method), then reverse the second half and compare it with the first half.
GET YOUR FREE
Coding Questions Catalog
