Reverse Linked List

Thought Process

To reverse a linked list, we can either use a recursive approach or an iterative approach:

Approach 1: Recursive Approach - Base case: If the list is empty or has only one node, return the head else recursively reverse the rest of the list and adjust the pointers to reverse the current node. Finally, return the new head of the reversed list.

Approach 2: Iterative Approach - Use three pointers: prev, curr, and tmp. Traverse the list, adjusting the next pointers to reverse the direction of the list. Finally, return the new head of the reversed list.

Approach 1: Recursive Approach

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

        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

Approach 2: Iterative Approach

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        ListNode* prev = nullptr;
        ListNode* curr = head;

        while(curr!=nullptr){
            ListNode* tmp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = tmp;
        }
        return prev;
    }
};

Code Complexity

Time Complexity: O(n)

Both approaches iterate through the list once, making them linear in time complexity.

Space Complexity: O(1) or O(n)

The iterative approach uses constant space, while the recursive approach uses stack space proportional to the length of the list.