Middle / split (Linked List — Fast & Slow Sub-pattern)

// Middle of a list: when fast reaches the end, slow is halfway.
// Even length → returns the SECOND middle (1→2→3→4 gives 3).
ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// Node just BEFORE the middle (to delete it or cut the list in two).
// Needs at least 2 nodes. Fast starts 2 ahead, so slow stops one node earlier.
ListNode* beforeMiddle(ListNode* head) {
    ListNode *slow = head, *fast = head->next->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}