Linked List — Reversal Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

// Full reversal: walk once, pointing each node back to the previous one.
// Returns the new head (the old tail).
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;                  // the reversed part so far (empty at first)
    ListNode* cur = head;                      // the next node to flip
    while (cur != nullptr) {
        ListNode* nxt = cur->next;             // 1. save the rest of the list BEFORE losing it
        cur->next = prev;                      // 2. flip this arrow
        prev = cur;                            // 3. the reversed part now starts at cur
        cur = nxt;                             // 4. move on to the saved node
    }
    return prev;                               // cur ran off the end, so prev is the old tail
}

// Sublist reversal: reverse nodes at positions left..right (1-based), keep the rest.
// Head insertion: walk to the node before the range, then pull the node after
// the pivot to the front of the range, one at a time.
ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(0, head);                   // a fixed node before head, so left = 1 is no special case
    ListNode* before = &dummy;
    for (int i = 1; i < left; i++) before = before->next;   // before = the node just before the range

    ListNode* pivot = before->next;            // the first node of the range; it stays put
    for (int i = left; i < right; i++) {       // right - left flips
        ListNode* moved = pivot->next;         // 1. the node that jumps to the front
        pivot->next = moved->next;             // 2. close the gap it leaves behind
        moved->next = before->next;            // 3. it points at the current front of the range
        before->next = moved;                  // 4. it becomes the new front
    }
    return dummy.next;                         // the dummy's next is the new head
}

// Groups of k: reverse each full block of k nodes; a short last block stays as it is.
// Count k nodes ahead first. If the block is full, reverse it, then join it to the
// previous block's tail (the old first node of this block is now its last).
ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode dummy(0, head);
    ListNode* groupPrev = &dummy;              // the node just before the current block

    while (true) {
        // 1. Is there a full block of k nodes starting after groupPrev?
        ListNode* kth = groupPrev;
        for (int i = 0; i < k && kth != nullptr; i++) kth = kth->next;
        if (kth == nullptr) break;             // fewer than k left: leave the rest alone

        ListNode* groupNext = kth->next;       // the node after this block (saved before relinking)
        ListNode* first = groupPrev->next;     // the old first node; it becomes the block's last

        // 2. Reverse the block with head insertion (same as the sublist template).
        ListNode* prev = groupNext;            // the reversed block must end at groupNext
        ListNode* cur = first;
        while (cur != groupNext) {
            ListNode* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }

        // 3. Join: the previous block now ends at the new first node (kth).
        groupPrev->next = kth;
        groupPrev = first;                     // the old first is this block's tail for the next round
    }
    return dummy.next;
}

// Split, reverse, and re-weave: L0 → Ln → L1 → Ln-1 → L2 → …
// Three steps. Find the end of the first half, reverse the second half,
// then interleave the two halves one node at a time.
void reorderList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return;

    // 1. Find the end of the first half (fast and slow). slow stops on the first middle.
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 2. Cut the list in two, then reverse the second half.
    ListNode* second = slow->next;
    slow->next = nullptr;                      // cut: without this the first half still runs into the second
    ListNode* prev = nullptr;
    while (second != nullptr) {
        ListNode* nxt = second->next;
        second->next = prev;
        prev = second;
        second = nxt;
    }
    second = prev;                             // head of the reversed second half (the old tail)

    // 3. Weave: take one node from the first half, then one from the second, until one runs out.
    ListNode* first = head;
    while (second != nullptr) {
        ListNode* f = first->next;             // save both continuations before relinking
        ListNode* s = second->next;
        first->next = second;                  // L0 → Ln
        second->next = f;                      // Ln → L1
        first = f;
        second = s;
    }
}