Watch 10 video solutions for Middle of the Linked List, a easy level problem involving Linked List, Two Pointers. This walkthrough by NeetCodeIO has 42,054 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |