Introduction
The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.
Problem Statement
In this problem, we are given two sorted linked lists, and we are asked to merge the two lists in such a way that the new merged list is in reverse order.
Problem Statement Understanding
Letβs try to understand this problem with the help of examples.
If the given linked lists are:
list 1: 3β7β10β14.
list 2: 12β13β15.
- According to the problem statement, we need to merge the list 1 and list 2 in such a way that the final merged list is in the reverse order.
- When we actually merge the list 1 and list 2, our merged list will be 3β7β10β12β13β14β15.
- And our output will be the reverse of this merged list, which is 15β14β13β12β10β7β3.
Taking another example, if the linked lists are:
list 1: 1β2β3β9.
list 2: 4β5β11β17.
- In this case, when we merge list 1 and list 2, our merged list will be 1β2β3β4β5β9β11β17.
- And our output will be the reverse of this merged list, which is: 17β11β9β5β4β3β2β1.
Some more examples
Sample Input 1:
- list 1: 1β3β5β7
- list 2: 2β4β6β8
Sample Output 1:
- 8β7β6β5β4β3β2β1
Sample Input 2:
- list 1: 2β5β10β15
- list 2: 3β6β7
Sample Output 2:
- 15β10β7β6β5β3β2
Now, I think from the above examples, the problem statement is clear. Letβs see how we can approach it.
Before moving to the approach section, try to think how you can approach this problem.
- If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.
Well, the most naive idea is:
- Reverse the first list.
- Reverse the second list.
- And then merge two reversed linked lists.
Using these above steps, we will get our required output.
Another similar approach is first to merge both the list and then finally reverse the merged list.
Both of the above approaches will work fine, but can we do this with some in-place algorithm and only one traversal using O(1) extra space?
- Letβs see the approach for the same.
Letβs move to the approach section.
Approach
This approach is based on a merge style process.
- First, we initialize the resultant linked list as empty.
- And then, traverse both the linked lists from beginning to end and compare the current nodes of both the linked lists and insert the smaller of two at the beginning of the resultant linked list.
- Finally, our resultant linked list will have the merged list in reverse order.
The following algorithm will explain the approach in detail.
Algorithm
- First, initialize the resultant linked list result as an empty list.
- Let h1 and h2 be the two pointers pointing to the head of list 1 and list 2, respectively.
- Now we will traverse the two given linked lists while(h1!=NULL && h2!=NULL).
- We will find the smaller of two nodes pointed by h1 and h2.
- After finding the smaller of the two nodes, we will insert the node with the smaller value at the front of the result list.
- Then we will move forward in the linked list with a smaller node value.
- If either of the linked lists is traversed completely, then insert all the remaining nodes of another list into the result list.
- Finally, after all these steps, we will have our merged list in reverse order.
Dry Run
Code Implementation
#includeusing namespace std; /* Node structure of linked list node */ struct Node { int data; struct Node* next; }; /* Using this function we will be merging both the linked list in such a way that merged list will be in reverse order */ Node* MergeSortedReverse(Node *h1, Node *h2) { if (h1==NULL && h2==NULL) return NULL; Node *result = NULL; while (h1 != NULL && h2 != NULL) { if (h1->data <= h2->data) { Node *temp = h1->next; h1->next = result; result = h1; h1 = temp; } else { Node *temp = h2->next; h2->next = result; result = h2; h2 = temp; } } while (h1 != NULL) { Node *temp = h1->next; h1->next = result; result = h1; h1 = temp; } while (h2 != NULL) { Node *temp = h2->next; h2->next = result; result = h2; h2 = temp; } return result; } /* Using this function we will be printing the linked list content */ void PrintingList(struct Node *Node) { while (Node!=NULL) { cout< data<<" -> "; Node = Node->next; } cout<<"NULL"< data = data; temp->next = NULL; return temp; } int main() { struct Node* result = NULL; Node *list1 = newNode(3); list1->next = newNode(7); list1->next->next = newNode(10); list1->next->next->next = newNode(14); Node *list2 = newNode(12); list2->next = newNode(13); list2->next->next = newNode(15); cout<<"Original linked list 1: "<
Output
Original linked list 1:
3 -> 7 -> 10 -> 14 -> NULL
Original linked list 2:
12 -> 13 -> 15 -> NULL
Merged list in reverse order:
15 -> 14 -> 13 -> 12 -> 10 -> 7 -> 3 -> NULL
Time Complexity: O(max(m,n)), where m, n are the size of Linked Lists.
[forminator_quiz id="5091"]
This blog tried to discuss how you can merge two sorted linked lists such that the merge list is in the reversed order with no extra space and linear time complexity. This is a basic problem and is good for strengthening your concepts in LinkedList and if you want to practice more such problems, you can checkout Prepbytes (Linked List).