Vansh Aggarwal

Posted on Apr 6

LeetCode Solution: 876. Middle of the Linked List

#leetcode #dsa #programming #tutorial

Race to the Middle! Unlocking LeetCode 876: Middle of the Linked List

Hey LeetCoders and aspiring developers! 👋 Vansh2710 here, ready to dive into another fun LeetCode challenge that's perfect for strengthening your understanding of linked lists. Today, we're tackling Problem 876: Middle of the Linked List.

This problem is a fantastic introduction to a super common and powerful technique for linked list manipulation. So, grab your favorite beverage, and let's unravel this together!

🧐 Problem Explanation: What are we actually doing?

Imagine you have a chain of connected boxes (that's a linked list!). Each box contains a number and a pointer (an arrow) to the next box in the chain. The head is the very first box.

Our mission is simple: find the box that's right in the middle of this chain.

If the chain has an odd number of boxes: There's clearly one middle box. We need to return that box and all the boxes that come after it.
- Example 1: head = [1, 2, 3, 4, 5]
  - The middle box is 3. We return [3, 4, 5].
If the chain has an even number of boxes: There are two "middle" boxes. The problem specifically asks us to return the second of these two middle boxes, and all boxes after it.
- Example 2: head = [1, 2, 3, 4, 5, 6]
  - The two middle boxes are 3 and 4. We need to return 4 (the second one) and everything after it: [4, 5, 6].

The constraints are pretty forgiving: the list will have between 1 and 100 nodes. This means we don't have to worry about super long lists for now, but our solution should ideally be efficient!

💡 Intuition: The "Aha!" Moment

How would you find the middle of a chain if you could only look at one box at a time and move forward?

A simple way might be:

Count all the boxes in the chain. Let's say there are N boxes.
Calculate the middle index. If N is 5, the middle is (5 / 2) + 1 = 3 (1-indexed). If N is 6, the middle is (6 / 2) + 1 = 4 (1-indexed, for the second middle).
Then, start from the beginning again and move (middle_index - 1) steps forward to reach the middle box.

This works, but it requires two passes through our linked list: one to count, and one to find the node. Can we do better? Can we find the middle in just one pass?

Think about two runners on a race track...

Imagine you have two runners starting at the same point.

One runner (slow) takes one step at a time.
The other runner (fast) takes two steps at a time.

If they both start from the beginning of the linked list, by the time the fast runner reaches the end of the list, where will the slow runner be?

Precisely! The slow runner will be exactly at the middle! Because the fast runner covers twice the distance in the same amount of time, when fast has reached the finish line, slow has only covered half the track. This is the Two Pointers (or Fast & Slow Pointers) technique!

🪜 Approach: Stepping Through the Solution

Let's formalize our two-pointer strategy:

Initialize two pointers:
- slow pointer, starting at head.
- fast pointer, also starting at head.
Traverse the list with both pointers:
- In each step of our loop:
  - Move slow one step forward: slow = slow->next;
  - Move fast two steps forward: fast = fast->next->next;
Determine the loop's stopping condition:
- The fast pointer is leading the race. It will reach the end first.
- We need to stop when fast or fast->next becomes nullptr (meaning fast has reached or gone past the end of the list).
- So, our loop continues while (fast != nullptr && fast->next != nullptr).
Why this works for both odd and even lists:
- Odd length list (e.g., [1, 2, 3, 4, 5]):
  - Start: slow=1, fast=1
  - Step 1: slow=2, fast=3
  - Step 2: slow=3, fast=5
  - fast->next is nullptr (after 5). The loop terminates. slow is at 3, which is our desired middle node.
- Even length list (e.g., [1, 2, 3, 4, 5, 6]):
  - Start: slow=1, fast=1
  - Step 1: slow=2, fast=3
  - Step 2: slow=3, fast=5
  - Step 3: slow=4, fast points to nullptr (after 6, so fast is nullptr in the next iteration if fast->next was checked first, or fast->next is nullptr if fast is 6 but fast->next is nullptr). The loop terminates. slow is at 4, which is the second middle node, as required!
Return slow: When the loop finishes, slow will be pointing to the middle node (or the second middle node for even-length lists).

This elegant solution finds the middle in a single pass!

💻 Code: Bringing it to Life

Here's the C++ implementation using the fast and slow pointer technique:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        // Loop until fast reaches the end of the list (or one node before the end)
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;          // slow moves one step
            fast = fast->next->next;    // fast moves two steps
        }

        // When fast reaches the end, slow will be at the middle
        return slow;
    }
};

⏱️ Space & Time Complexity Analysis

Let N be the number of nodes in the linked list.

Time Complexity: O(N)
- We traverse the linked list exactly once. The fast pointer covers N nodes (or slightly less/more depending on N's parity), and the slow pointer covers N/2 nodes. Regardless, the number of operations scales linearly with the number of nodes.
Space Complexity: O(1)
- We only use a constant amount of extra space for our slow and fast pointers, regardless of the list's size. No auxiliary data structures are used.

This is an optimal solution in terms of both time and space complexity!

🚀 Key Takeaways

Two Pointers (Fast & Slow Pointers): This is a cornerstone technique for linked list problems! It's incredibly useful for finding the middle, detecting cycles, or finding the k-th node from the end.
Single Pass Efficiency: By using two pointers moving at different speeds, we can often solve problems that might otherwise require multiple passes, saving computation time.
Edge Cases for Linked Lists: Always consider empty lists, single-node lists, and two-node lists when designing your logic. Here, fast != nullptr && fast->next != nullptr elegantly handles these.

That's a wrap for Problem 876! I hope this deep dive into the "Middle of the Linked List" problem has demystified the fast and slow pointer technique for you. Keep practicing, and you'll master these patterns in no time!

Happy Coding! ✨

Authored by Vansh2710
Published: 2026-04-06 23:32:58

DEV Community