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:
[1, 100].1 <= Node.val <= 100Problem 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.
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.
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.
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.
Time Complexity: O(n) for two full passes through the list.
Space Complexity: O(1) as only a few extra variables are used.
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).
| 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 | — |
| 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 |
Middle of the Linked List - Leetcode 876 - Python • NeetCodeIO • 42,054 views views
Watch 9 more video solutions →Practice Middle of the Linked List with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor