Middle of the Linked List

How it works

The fast and slow pointer technique finds the middle in a single pass. The slow pointer moves one step at a time, while the fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer will be at the middle. This works because the fast pointer covers twice the distance in the same number of iterations.

Steps

1. Initialize both slow and fast pointers at the head.
2. While fast is not null and fast.next is not null:
   • Move slow one step forward.
   • Move fast two steps forward.
3. Return slow, which now points to the middle node.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Incorrect Loop Condition for Fast Pointer

When using the fast and slow pointer technique, the loop condition must check both fast and fast.next before advancing. Checking only fast can cause a null pointer exception when trying to access fast.next.next. The correct condition is while (fast != null && fast.next != null).

Off-by-One Error with Even-Length Lists

For lists with an even number of nodes, there are two middle nodes. The problem typically asks for the second middle node, but some implementations accidentally return the first. Ensure your pointer movement logic returns the correct middle based on the problem requirements.

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

/**
 * 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;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};