Middle of the Linked List | Leetcode 876 | Tortoise Hare Approach

The “Middle of the Linked List” problem is a classic linked list question that helps you understand traversal techniques and the famous two-pointer approach.

In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with detailed explanations, code comments, dry runs, and clear reasoning.

Here’s the [Problem Link] to begin with.

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

Brute Force Solution (Count then Traverse)

Intuition and Approach

Let’s think about this problem step by step in the most straightforward way:

1. Why do we need to count first?
   To find the middle of a linked list, we need to know how many nodes there are. Unlike arrays where we can directly access elements by index, linked lists require us to traverse from the beginning to reach any specific position.
2. How do we find the middle position?
   Once we know the total count n, the middle position is at index n // 2 (0-indexed). This works for both odd and even lengths:
   • For odd length (e.g., 5 nodes): middle is at index 5//2 = 2 (3rd node)
   • For even length (e.g., 6 nodes): middle is at index 6//2 = 3 (4th node, which is the second middle)
3. Two-pass approach:
   • First pass: Count all nodes by traversing the entire list
   • Second pass: Start from head again and move exactly n // 2 steps to reach the middle
4. Why does this work?
   Since we know the exact position of the middle node, we can directly navigate to it. This approach is reliable and easy to understand.
5. When should you use this approach?
   This method is great when you want to be absolutely clear about what you’re doing, or when you need to know the total length for other purposes too.

Code Implementation

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        n = 0
        temp = head
        # First pass: count the total number of nodes
        while temp:
            n += 1                          # increment counter
            temp = temp.next                # move to next node
        
        temp = head
        # Second pass: move to the middle position
        for i in range(n // 2):
            temp = temp.next                # move forward n//2 steps
        return temp                         # return the middle node

Code Explanation

Step 1: Count the nodes

• We use a temporary pointer temp to traverse the list without losing the original head
• We start counting from 0 and increment for each node we visit
• When temp becomes None, we’ve counted all nodes

Step 2: Find the middle

• We reset temp to point back to the head
• We move forward exactly n // 2 steps using a for loop
• After the loop, temp points to the middle node

Step 3: Return the result

• We return temp, which now points to the middle node

Dry Run

Let’s trace through this with an example:

Input:
head = [1]

First Pass (Counting):

• temp = 1, n = 1
• temp = 2, n = 2
• temp = 3, n = 3
• temp = 4, n = 4
• temp = 5, n = 5
• temp = None, exit loop, total n = 5

Second Pass (Finding Middle):

• n // 2 = 5 // 2 = 2, so we need to move 2 steps
• temp = 1 (start)
• i = 0: temp = 2 (move 1 step)
• i = 1: temp = 3 (move 2 steps)
• Return node with value 3

Final Output:
Node with value 3 (and the rest of the list: )

Time and Space Complexity

• Time Complexity: O(n) + O(n/2) = O(n)
  First pass takes O(n) to count, second pass takes O(n/2) to reach middle
• Space Complexity: O(1)
  Only using a few variables regardless of input size

Conclusion

The brute force approach is straightforward and easy to understand. It’s perfect for beginners to grasp the concept, though it requires two passes through the list.

Optimal Solution (Two Pointers / Fast and Slow)

Intuition and Approach

Now let’s think about a more elegant solution using the two-pointer technique:

1. The core idea: Different speeds
   Imagine two people running on a track. If one person runs twice as fast as the other, when the faster person completes the track, the slower person will be exactly at the middle. This is the exact principle we use here.
2. Why does the two-pointer approach work?
   • Slow pointer: Moves 1 step at a time
   • Fast pointer: Moves 2 steps at a time
   • When the fast pointer reaches the end, the slow pointer will be at the middle
   • This is because the fast pointer covers twice the distance in the same time
3. Mathematical reasoning:
   • If the list has n nodes, the middle is at position n/2
   • Fast pointer moves 2 steps per iteration, slow pointer moves 1 step per iteration
   • After k iterations: fast pointer is at position 2k, slow pointer is at position k
   • When fast pointer reaches the end (2k = n), slow pointer is at k = n/2, which is the middle
4. Handling different cases:
   • Odd length: Fast pointer reaches the last node, slow pointer is at exact middle
   • Even length: Fast pointer goes beyond the list, slow pointer is at the second middle node
5. Why is this optimal?
   • Single pass: We only traverse the list once
   • No counting needed: We don’t need to know the total length beforehand
   • Constant space: Only using two pointers
6. When should you use this approach?
   This is the preferred method for interviews and production code because it’s efficient and demonstrates good understanding of pointer manipulation.

Code Implementation

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = head                         # slow pointer starts at head
        fast = head                         # fast pointer starts at head
        
        # Move until fast pointer reaches the end
        while fast and fast.next:
            slow = slow.next                # slow moves 1 step
            fast = fast.next.next           # fast moves 2 steps
        
        return slow                         # slow is now at the middle

Code Explanation

Step 1: Initialize pointers

• Both slow and fast pointers start at the head of the list
• This ensures they both begin the race from the same starting point

Step 2: The main loop condition

• while fast and fast.next: ensures we don’t go out of bounds
• fast checks if the current node exists
• fast.next checks if the next node exists (needed since fast moves 2 steps)

Step 3: Move pointers

• slow = slow.next: slow pointer moves 1 step forward
• fast = fast.next.next: fast pointer moves 2 steps forward
• This happens in each iteration until fast reaches the end

Step 4: Return result

• When the loop ends, slow is pointing to the middle node
• We return slow as the answer

Why the loop condition works:

• Odd length: Fast pointer will be at the last node, and fast.next will be None, so loop stops
• Even length: Fast pointer will be None (went past the end), so loop stops
• In both cases, slow pointer ends up at the correct middle position

Dry Run

Let’s trace through this with two examples:

Example 1 (Odd length):
head = [1]

• Initial: slow = 1, fast = 1
• Iteration 1: slow = 2, fast = 3
• Iteration 2: slow = 3, fast = 5
• Check condition: fast = 5 (exists), fast.next = None (doesn’t exist)
• Loop ends: Return slow = 3

Example 2 (Even length):
head = [1]

• Initial: slow = 1, fast = 1
• Iteration 1: slow = 2, fast = 3
• Iteration 2: slow = 3, fast = 5
• Iteration 3: slow = 4, fast = None (went past the end)
• Check condition: fast = None (doesn’t exist)
• Loop ends: Return slow = 4

Time and Space Complexity

• Time Complexity: O(n/2) = O(n)
  We traverse at most half the list (when fast pointer reaches the end)
• Space Complexity: O(1)
  Only using two pointer variables

Conclusion

The optimal solution using two pointers is elegant and efficient. It demonstrates a deep understanding of linked list traversal and is the preferred approach for coding interviews.

Final Thoughts

The “Middle of the Linked List” problem is an excellent way to learn about linked list traversal techniques:

• Start with the brute force approach to understand the fundamentals
• Master the two-pointer technique for optimal performance and to impress in interviews
• The two-pointer approach is a powerful pattern that appears in many linked list problems

Understanding both approaches will make you a stronger problem solver and help you tackle more complex linked list challenges.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.