DSA Pattern: Reversing a Linked List

Reversing a linked list is the quintessential "pointer manipulation" problem. It can be solved either iteratively or recursively.

Iterative Solution (O(1) Space)

Maintain three pointers: prev, curr, and nextTemp. In each step, we flip the curr->next pointer to point to prev.

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

Recursive Solution (O(N) Space)

The recursive version is more elegant but uses O(N) stack space.

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* p = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return p;
}