Can we reverse a linked list in less than O(n)?
It doesn’t look possible to reverse a simple singly linked list in less than O(n). A simple singly linked list can only be reversed in O(n) time using recursive and iterative methods.
A memory-efficient doubly linked list with head and tail pointers can also be reversed in O(1) time by swapping head and tail pointers.
A doubly linked list with head and tail pointers can also be reversed in O(1) time by swapping head and tail pointers, but we would have to traverse the list in forward direction using prev pointer and reverse direction using next pointer which may not be considered valid.
This article is contributed by Abhishek. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Reverse a linked list
Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.
Examples:
Input: Head of following linked list
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULLInput: Head of following linked list
1->2->3->4->5->NULL
Output: Linked list should be changed to,
5->4->3->2->1->NULLInput: NULL
Output: NULL
Input: 1->NULL
Output: 1->NULL
Can we write an algorithm to reverse the given linked list in less than O(n) runtime ?
No, we cannot reverse a linked list in O(n) time, because each pointer must be reversed or values must be interchanged to reverse a linked list. To do that we need to reach the last node which takes a pointer to reach last node which takes O(n) time.
It can`t even be done by using recursive and iterative methods.
But you can reverse a memory efficient doubly linked list in O(1) time, it`s just by swapping Tail and Head pointers.
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:
- Return the head pointer of the reversed list i.e. return restReversedPart.
- Base Case: if(head == NULL || head.next == NULL) then return Null.
Pseudo-CodeListNode 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.
- 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:
- return previous pointer which will be the head of the reversed list.
Pseudo-CodeListNode 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!!