Reverse A Linked List

15 Apr 2022

Approach: Iteration

It is possible to reverse a linked list by reversing the reference direction of the linked list. First, we take a prev node and assign nullptr to it. This pointer will be assigned as head node’s reference as it will become the last node in the linked list when the list is reversed.

Now, we start iterating over the linked list untill current != nullptr. We take a temporary temp node to store the reference of current->next. To iterate, we move forward by assigning current to prev node and finally assign previously stored temp to current.

Lastly, we return the head prev.

 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) {}
 };

Above is the definition of a signly-linked-list.

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* current = head;
    
    while(current){
        ListNode* temp = current->next;
        current->next = prev;
        prev = current;
        current = temp;
    }
    return prev;
}

Time complexity: $ O(n) $

Space Complexity: $ O(1) $

Approach: Recursive

ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode* p = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return p;
}

Time complexity: $ O(n) $

Space complexity: $ O(n) $