206. Reverse Linked List

• Link: https://leetcode.com/problems/reverse-linked-list/

Question

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

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Approach 1: Brute Force

Intuition

• Stack: Last In First Out (LIFO)

Algorithm

1. Create a stack<int> s to hold the values of the linkedlist.
2. Declare ListNode* curr & initialize with head.
3. Loop through the LL using curr pushing value of each node into the stack.
4. Reinitialize curr = head
5. Loop through the LL again replacing the value of curr with the value at the top of the stack & pop the stack.
6. Return the head

Code

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        stack<int> s;

        ListNode* curr = head;
        while (curr) {
            s.push(curr->val);
            curr = curr->next;
        }

        curr = head;
        while (curr) {
            int newVal = s.top();
            s.pop();
            curr->val = newVal;

            curr = curr->next;
        }

        return head;
    }
};

Complexity Analysis

• Time Complexity: $O(2N)=O(N)$
• Space Complexity: $O(N)$ (Stack space)

Approach 2: Optimal 1 (iterative)

Intuition

• Changing the links in-place

Algorithm

1. Declare & initialize ListNode* curr = head.
2. Declare & initialize ListNode* prev = NULL.
3. Loop through the LL till curr != NULL.
   1. Declare & initialize ListNode* next = curr->next; so the reference for the next node is not lost when we change the links.
   2. curr->next will point to prev
   3. prev will now be curr
   4. curr will now be next
4. Now, curr == NULL, but prev will point to the last node which will be the new head.
5. Return prev.

Code

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

        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }
};

Complexity Analysis

• Time Complexity: $O(N)$
• Space Complexity: $O(1)$

Approach 3: Optimal (Recursive)

Algorithm

1. Base case: if (head == NULL || head->next == NULL) return head.
2. Declare & initialize ListNode* newHead with recursive call for head->next.
3. Reverse the link, head->next->next = head.
4. head->next = NULL.
5. Return newHead.

Code

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

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

        head->next->next = head;
        head->next = NULL;

        return newHead;
    }
};

Complexity Analysis

• Time Complexity: $O(N)$
• Space Complexity: $O(1)$