Middle of the Linked List

LeetCode 876: Middle of the Linked List Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes the Fast and Slow Pointer technique to locate the middle node in a single traversal by moving one pointer twice as fast as the other.

The LeetCode 876 problem asks us to find the middle node of a singly linked list. If the list has an odd number of nodes, there is a single middle node. If the list has an even number of nodes, there are two middle nodes, and the problem specifies that we must return the second one. This is a fundamental problem in the Middle of the Linked List category, often used to test understanding of pointer manipulation and traversal efficiency.

Brute Force Approach for Middle of the Linked List

The most intuitive way to solve this problem is a two-pass approach. First, we need to know the total length of the list to determine which index constitutes the "middle."

1. First Pass: Traverse the entire linked list from the head to the end, counting the number of nodes. Let this count be $N$.
2. Calculation: Determine the middle index using integer division: $\text{mid} = N / 2$.
3. Second Pass: Traverse the list again, starting from the head, and move forward $\text{mid}$ times.
4. Result: Return the node at the current position.

Pseudo-code:

function middleNode(head):
    length = 0
    current = head
    while current is not null:
        length++
        current = current.next
    
    mid_index = length / 2
    current = head
    for i from 0 to mid_index - 1:
        current = current.next
        
    return current

Time Complexity: $O(N)$ + $O(N/2) \approx O(N)$. We traverse the list 1.5 times on average. Why it fails (Context): While this solution is valid and passes LeetCode test cases (since constraints are small, $N \le 100$), it is not the "optimal" solution expected in interviews. It requires two traversals. In systems where data is streamed or memory access is expensive, a single-pass solution is strictly preferred.

Algorithm Strategy: Two Pointer Patterns

1. Initialization: Create two pointers, slow and fast, both pointing to the head of the linked list.
2. Traversal: Enter a loop that continues as long as fast is not null and fast.next is not null. This condition ensures that fast can safely make a two-step jump.
3. Pointer Updates:
   • Move slow one step forward: slow = slow.next.
   • Move fast two steps forward: fast = fast.next.next.
4. Termination: When the loop terminates, the fast pointer has reached the end. Consequently, the slow pointer is positioned at the middle node.
5. Return: Return the slow pointer.

This strategy automatically handles both odd and even lengths correctly due to the floor behavior of integer division implied by the step mechanics.

Execution Flow

Consider an even-length list: [1, 2, 3, 4, 5, 6]. We expect the output to be 4.

1. Start:
   • slow points to 1.
   • fast points to 1.
2. Iteration 1:
   • slow moves to 2.
   • fast moves to 3.
   • State: Valid, continue.
3. Iteration 2:
   • slow moves to 3.
   • fast moves to 5.
   • State: Valid, continue.
4. Iteration 3:
   • slow moves to 4.
   • fast moves to NULL (via 5 -> 6 -> NULL).
   • State: fast is NULL, loop terminates.
5. Result: Return slow, which is 4. Correct.

Consider an odd-length list: [1, 2, 3, 4, 5]. We expect the output to be 3.

1. Start: slow at 1, fast at 1.
2. Iteration 1: slow at 2, fast at 3.
3. Iteration 2: slow at 3, fast at 5.
4. Check: fast is at 5. fast.next is NULL. Loop terminates.
5. Result: Return slow, which is 3. Correct.

Proof of Correctness

Let $L$ be the length of the linked list. Let $S$ be the distance covered by the slow pointer. Let $F$ be the distance covered by the fast pointer.

The invariant maintained is $F = 2 \times S$.

Case 1: Odd Length ($2k + 1$) The fast pointer stops at the last node (index $2k$). $F = 2k$. Therefore, $S = k$. Index $k$ corresponds to the exact middle element (0-indexed).

Case 2: Even Length ($2k$) The fast pointer moves past the last node to NULL (index $2k$). $F = 2k$. Therefore, $S = k$. Index $k$ corresponds to the $(k+1)$-th node, which is the second middle node as required.

Pattern Reuse Notes

The Two Pointer pattern used here is highly versatile. Similar logic applies to:

• LeetCode 19: Remove Nth Node From End of List - Uses two pointers with a fixed delay to find a node relative to the end.
• LeetCode 2095: Delete the Middle Node of a Linked List - Uses the exact same "slow and fast" logic to locate the predecessor of the middle node.

Mastering the movement of pointers at different speeds or with fixed gaps is essential for optimal linked list manipulation.

Reference Implementation

C++ Solution for LeetCode 876

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* middleNode(ListNode* head) {
14        ListNode* slow = head;
15        ListNode* fast = head;
16        
17        // Loop until fast reaches the end (even case) or last node (odd case)
18        while (fast != nullptr && fast->next != nullptr) {
19            slow = slow->next;       // Move 1 step
20            fast = fast->next->next; // Move 2 steps
21        }
22        
23        return slow;
24    }
25};

Java Solution for LeetCode 876

1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode() {}
7 *     ListNode(int val) { this.val = val; }
8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11class Solution {
12    public ListNode middleNode(ListNode head) {
13        ListNode slow = head;
14        ListNode fast = head;
15        
16        // Traverse with different speeds
17        while (fast != null && fast.next != null) {
18            slow = slow.next;
19            fast = fast.next.next;
20        }
21        
22        return slow;
23    }
24}

Python Solution for LeetCode 876

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, val=0, next=None):
4#         self.val = val
5#         self.next = next
6
7class Solution:
8    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
9        slow = head
10        fast = head
11        
12        # Check fast and fast.next to ensure we can make a double jump
13        while fast and fast.next:
14            slow = slow.next
15            fast = fast.next.next
16            
17        return slow