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?
Suggested Problems to Solve
- Reverse a Linked List from position M to N.
- Reverse a Stack.
- Reverse a Linked List in groups of given size.
- Reverse a Linked List using Stack.
Happy Coding! Enjoy Algorithms!!