Problem Statement

Given the head of a singly linked list, reverse the order of all nodes in the list and return the head of the reversed list.

Sample Input 1:

head = [1,2,3,4,5]

Sample Output 1:

[5,4,3,2,1]

Sample Input 2:

head = [1,2]

Sample Output 2:

[2,1]

Sample Input 3:

head = []

Sample Output 3:

[]

Constraints:

• The number of nodes in the list ranges from 0 to 5000
• Each node's value falls in the range [-5000, 5000]

Iterative In-Place Reversal

This approach uses two traversal pointers to rewire node connections as we move through the list from head to tail. We initialize a current pointer starting at the input head, and a prior pointer set to nullptr (the original head will become the tail of the reversed list, which points to null). For each iteration, we first store the reference to the curent node's unprocessed next node, as we will lose access to the remainder of the list once we modify the current->next pointer. We then rewire current->next to point to the prior node, shift the prior pointer to the current node, and set current to the stored next node. The loop terminates when current points to null, at which point prior holds the address of the new reversed list head.

/**
 * 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* reverseList(ListNode* head) {
        ListNode* next_stored = nullptr;
        ListNode* prior = nullptr;
        ListNode* current = head;
        
        while (current != nullptr) {
            next_stored = current->next;
            current->next = prior;
            prior = current;
            current = next_stored;
        }
        
        return prior;
    }
};

Complexity Analysis:

• Time Complexity: O(n), where n is the length of the linked list. We traverse every node exactly once.
• Space Complexity: O(1), as we only use a fixed number of pointer variables regardless of input size.

Recursive Implementation (Double Pointer Equivalent)

This implementation mirrors the logic of the iterative double pointer approach, replacing the explicit loop with recursive function calls. We use a helper function that accepts the prior node and current node as parameters, initialized to nullptr and the input head respectively. The base case triggers when current is null, returning prior as the new list head. For each recursive step, we store the next node of current, rewire current->next to point to prior, then invoke the helper with current as the new prior and the stored next node as the new current.

/**
 * 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 {
private:
    ListNode* reverseHelper(ListNode* prior, ListNode* current) {
        if (current == nullptr) return prior;
        ListNode* next_stored = current->next;
        current->next = prior;
        return reverseHelper(current, next_stored);
    }
public:
    ListNode* reverseList(ListNode* head) {
        return reverseHelper(nullptr, head);
    }
};

Complexity Analysis:

• Time Complexity: O(n), as each node is processed exactly once across recursive calls.
• Space Complexity: O(n), where n is the length of the list. The recursion call stack will hold up to n frames for a full list traversal.

Tail-First Recursive Reversal

This approach reverses the list starting from the tail node first, working backwards to the original head. The base cases handle empty lists or single-node lists, which are already reversed. We first recursively reverse the sublist starting from the node immediately after the current head. Once we receive the head of the reversed sublist, we set the next pointer of the original head's next node (now the tail of the reversed sublist) to point back to the original head, then set the original head's next pointer to null to make it the new tail of the fully reversed list. We return the head of the reversed sublist as the final result.

/**
 * 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* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* reversed_sublist_head = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return reversed_sublist_head;
    }
};

Complexity Analysis:

• Time Complexity: O(n), as each node is processed exactly once.
• Space Complexity: O(n), due to the recursion call stack that can grow up to n levels deep.