Difficulty: Easy, Asked-in: Microsoft, Amazon, Adobe, Qualcomm.
Key takeaway: The basic linked list question to learn pointer manipulation and problem-solving using iteration and recursion. We can find many similar questions related to reversing various parts of the linked list.
A head pointer of a linked list is given, write a program to reverse the linked list. We need to reverse the list by changing the links between nodes.
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Input: 1->2->NULL
Output: 2->1->NULL
One idea is to traverse the linked list and update each node’s next pointer to point to the previous node. Keep track of the previous node and, before changing the current node’s next pointer, save the next node so you can continue traversing the list.
So at each iteration, we partially grow the size of the reversed linked list by 1 and keep updating the nodes using three pointers: one for tracking the current node, one for the previous node, and one for the next node.
We iterate through the linked list until curr becomes NULL and keep changing each node's next pointer to its previous node. During this process, we update curr, prev and forw pointers:
reverseLinkedList(head)
if head == NULL
return NULL
curr = head
prev = NULL
forw = NULL
while curr != NULL
forw = curr -> next
curr -> next = prev
prev = curr
curr = forw
return prevWe explore each node and perform constant operations at each iteration. So, the time complexity = n*O(1) = O(1). We use constant extra space, so the space complexity is O(1).
The critical question is: Can we solve this problem using recursion? In other words, how can we solve reversing a linked list problem using the solution of its smaller subproblems? Let's think.
Suppose the length of the linked list is n. Now we divide the linked list into two parts: The head node and the remaining linked list of size n - 1 (smaller sub-problem). We recursively reverse the remaining linked list of size n - 1 by calling the same function with head->next as an input parameter. Now this will return the head pointer of the reversed list of size n - 1 i.e. restListHead = reverseLinkedList (head->next).
After this, the head node will still point to the last node of the reversed list of size n - 1. In other words, the next node of the head will be the last node of the reversed list of size n - 1. So for the complete reversal, the head should be the last node. So, we do this operation to ensure this: head->next->next = head, head->next = NULL.
Base case: if (head == NULL || head->next == NULL), return NULL.
reverseLinkedList(head)
if head == NULL OR head -> next == NULL
return head
restListHead = reverseLinkedList(head -> next)
head -> next -> next = head
head -> next = NULL
return restListHeadWe are recursively solving the problem of size n with a smaller sub-problem of size n - 1.
Recurrence relation: T(n) = T(n - 1) + c.
Enjoy learning, Enjoy algorithms!