Reverse Linked List

Practice here

Given the head of a singly linked list, reverse the list, and return the reversed list.

Iterative Solution#

Analogy: Like flipping a chain link by link as you walk along it.

Maintain three pointers: prev (initially null), curr (current node), and next (lookahead). In each step, save curr->next in next, redirect curr->next to prev, then advance both prev and curr forward. After the loop prev points to the new head. This is O(1) space because no auxiliary structure is needed.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* frontNode = head;
        ListNode* node = head;
        ListNode* tailNode = NULL;

        while(frontNode){
            node = frontNode;
            frontNode = frontNode->next;
            node->next = tailNode;
            tailNode = node;
        }

        return node;
    }
};

Time Complexity: O(n), n-> number of nodes

Space Complexity: O(1)

Recursive Solution#

Analogy: Like walking to the end of the chain, then flipping the links backward on your way back.

Recurse all the way to the last node, which becomes the new head. On the way back up the call stack, make each node's next pointer the previous node: head->next->next = head; head->next = NULL. The new head propagates back up unchanged. The trade-off vs. the iterative approach is O(n) stack space for the recursion depth.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next)
            return head;
        
        ListNode* newHead = reverseList(head->next);

        ListNode* front = head->next;
        front->next = head;
        head->next = NULL;

        return newHead;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)