206. Reverse Linked List.md

206. Reverse Linked List | C++ Solution | Three Pointers | Stack | Optimized Approach

Intuition

The problem is asking to reverse a singly linked list. The first thought is to use three pointers: one to keep track of the previous node, one for the current node, and one for the next node. We then iteratively reverse the pointers from the current node to the previous node until we reach the end of the list.

Note:

• The problem is asking to reverse a singly linked list.
• The pointers of the linked list have to be reversed, not the values.

Approach

1. Stack: We can use a stack to store the nodes of the list. We first push all the nodes of the list onto the stack. We then pop the nodes from the stack and connect them in reverse order. We return the head of the reversed list.

2. Three Pointers: We first initialize three pointers: previous to NULL, current to the head of the list, and forward to NULL. We then enter a loop that continues until current is NULL. In each iteration of the loop, we move forward to the next node, reverse the pointer from current to previous, move previous to current, and move current to forward. After the loop, we delete current and forward and return previous, which is now the head of the reversed list.

Complexity

• Stack:

  • Time complexity: $O(n)$,
  • Space complexity: $O(n)$.

• Three Pointers:

  • Time complexity: $O(n)$,
  • Space complexity: $O(1)$.

Code

1. Stack:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        stack<ListNode*> s;
        ListNode* current = head;
        while (current != NULL) {
            s.push(current);
            current = current->next;
        }

        ListNode* dummy = new ListNode(0);
        current = dummy;
        while (!s.empty()) {
            current->next = s.top();
            s.pop();
            current = current->next;
        }
        current->next = NULL;

        return dummy->next;
    }
};

2. Three Pointers:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* previous = NULL;
        ListNode* current = head;
        ListNode* forward = NULL;

        while (current != NULL) {
            forward = current->next;
            current->next = previous;
            previous = current;
            current = forward;
        }

        delete current;
        delete forward;

        return previous;
    }
};