Reverse a Linked List

Difficulty:Medium

Asked in: Microsoft, MakeMyTrip, Adobe, Amazon

Understanding the Problem: →

Given a linked list pointed by a head node as input, your task is to reverse the linked list. After the reversal, The head data should become the last data element pointing to null. This should be done by de-linking the nodes and again linking it in reverse order.

For example:

Input: 2→3→4→5→6→7→NULL

Output: 7→6→5→4→3→2→NULL

Similarly

Input: 21→32→43→54→65→76→NULL

Output: 76→65→54→43→32→21→NULL

Possible follow-up questions to ask the interviewer:

Do we have to print the Linked List in reverse order?( Ans: No, just return the head of the reversed Linked List.)
What if only one node is given in input?( Ans: Just output that node )

Solutions

Solution idea

The idea here is to de-link a node from its previous node and add the previous node in front of the current node. We will follow the same approach for all the node and finally our new reversed Linked List will be ready. This idea can be implemented in two ways →

Recursive Solution
Iterative Solution

Recursive Solution

Solution steps

We can divide the linked list with n nodes into two parts: head and the rest of the linked list with n-1 nodes (Smaller problem ).
Recursively reverse the linked list with (n-1) nodes and return the head pointer of this part i.e. restReversedPart. After the reversal, the next node of the head will be the last node and the head will be pointing to this node.
But for the complete reversal of the list, the head should be the last node. So, do the following operations to ensure this:

    head.next.next = head     
    head.next = NULL

Return the head pointer of the reversed list i.e. return restReversedPart.
Base Case: if(head == NULL || head.next == NULL) then return Null.

Pseudo-Code

ListNode reverseList(ListNode head)

{
    if(head == NULL || head.next == NULL)
       return NULL
    ListNode restReversedPart= reverseList(head.next)
    head.next.next = head
    head.next = NULL
    return restReversedPart

Complexity Analysis

Recurrence relation: T(n) = T(n-1) + O(1)
Time Complexity = O(n), where n is the length of the Linked List
Space Complexity = O(n), for recursion stack space. (Think!)

Iterative Approach

Solution steps

We will take three pointers named current , previous and nextNode and will initialize them.

ListNode current = head      
ListNode previous = NULL      
ListNode nextNode = NULL

We will iterate over the linked list untill current is not equal to NULL and do the following update in every step of the iteration:

nextNode = current.next         
current.next = previous         
previous = current         
current = nextNode

return previous pointer which will be the head of the reversed list.

Pseudo-Code

ListNode reverseList(ListNode head)
{
     if(head == NULL)
        return NULL
     ListNode current = head
     ListNode previous = NULL
     ListNode nextNode = NULL
     while(current != NULL)
     {
        nextNode = current.next
        current.next = previous
        previous = current
        current = nextNode
     }
     return previous
}

Complexity Analysis

Time Complexity = O(n), where n is the length of the Linked List

Space Complexity = O(1)

Critical ideas to think!

Can we reverse a Linked List in less than O(n) time? Impossible right? What if the Linked List is doubly Linked List.
Can we use Stack for reversing the Linked List? If Yes, what will be the Complexity?