Middle of the Linked List - Solution & Explanation
Problem Statement
Given the head of a singly linked list, return the middle node of the linked list.
If there are 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 of the list is node 3.
Example 2:
Input: head = [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
Constraints:
- The number of nodes in the list is in the range
[1, 100]. 1 <= Node.val <= 100
Approach Overview
Problem Overview: Given the head of a singly linked list, return the middle node. If the list has two middle nodes (even length), return the second middle node. The task is a classic traversal problem on a linked list where you must locate the midpoint without modifying the structure.
Approach 1: List Length Calculation (O(n) time, O(1) space)
This approach performs two passes over the list. First, iterate through the entire list and count the number of nodes. Once you know the length n, compute the middle index n / 2. Then iterate again from the head until you reach that index and return the node. The idea is straightforward: determine the exact midpoint using the total size, then walk directly to it. This approach is simple to reason about and useful when the length of the list is already needed for other operations.
Approach 2: Two-pointer Technique (Slow and Fast) (O(n) time, O(1) space)
This method uses the classic two pointers technique. Initialize two pointers: slow and fast, both starting at the head. Move slow one step at a time while fast moves two steps at a time. When fast reaches the end of the list (or null), slow will be positioned exactly at the middle node. The key insight is that the fast pointer covers the list twice as quickly, so when traversal finishes, the slow pointer has completed half the distance.
This technique works naturally for both odd and even-length lists. In an even-length list, the fast pointer reaches the end while the slow pointer lands on the second middle node, which matches the problem requirement. The algorithm requires only a single traversal and constant extra memory.
Recommended for interviews: The slow–fast pointer method is the expected solution in most interviews. It demonstrates strong understanding of pointer manipulation in linked lists and shows you recognize common traversal patterns. The length-counting method is still useful as a baseline approach and proves you can reason about list structure, but the two-pointer technique highlights stronger algorithmic thinking.
Approach 1: Two-pointer Technique (Slow and Fast)
This technique uses two pointers, 'slow' and 'fast'. Both start at the head of the list. The 'slow' pointer progresses one node at a time while the 'fast' pointer moves two nodes at a time. When the 'fast' pointer reaches the end of the list, the 'slow' pointer will be at the middle node. This works because the 'fast' pointer traverses the list twice as fast as the 'slow' pointer, thus splitting the path lengthwise in half.
In C, we define a simple singly linked list structure and implement the two-pointer approach to find the middle node. The 'slow' pointer advances one step while the 'fast' pointer advances two steps, and once 'fast' reaches the end, 'slow' will be pointing at the middle node.
Complexity
Time Complexity: O(n), where n is the number of nodes in the list, because we are iterating through the list once.
Space Complexity: O(1), since we are using a constant amount of space.
Approach 2: List Length Calculation
This approach involves two passes over the list. The first pass calculates the total number of nodes. In the second pass, we traverse halfway through the list to reach the middle node by stopping at n/2, where n is the number of nodes. This explicitly determines the node that marks the middle of the list.
This C implementation counts the nodes in a linked list using an initial loop, then follows a second traversal that stops at the mid-point to return the middle node.
Complexity
Time Complexity: O(n) for two full passes through the list.
Space Complexity: O(1) as only a few extra variables are used.
Approach 3: Fast and Slow Pointers
We define two pointers fast and slow, both initially pointing to the head of the linked list.
The fast pointer fast moves two steps at a time, while the slow pointer slow moves one step at a time. When the fast pointer reaches the end of the linked list, the node pointed to by the slow pointer is the middle node.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-pointer Technique (Slow and Fast) | Time Complexity: O(n), where n is the number of nodes in the list, because we are iterating through the list once. |
| List Length Calculation | Time Complexity: O(n) for two full passes through the list. |
| Fast and Slow Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| List Length Calculation | O(n) | O(1) | When simplicity is preferred or when the list length is already being computed |
| Two-pointer Technique (Slow and Fast) | O(n) | O(1) | Best general solution; single traversal and commonly expected in interviews |
Video Solution
Middle of the Linked List - Leetcode 876 - Python • NeetCodeIO • 43,842 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Middle of the Linked List easy or hard?
Middle of the Linked List Python/Java solution
How to solve Middle of the Linked List in O(n)?
What is the best approach for Middle of the Linked List?
Is Middle of the Linked List asked at Google/Amazon/Meta?
What data structure is used in Middle of the Linked List?
What is the time complexity of Middle of the Linked List?
Ready to solve this problem?
Practice Middle of the Linked List with our built-in code editor and test cases.
Practice on FleetCode