Linked List Pattern |Merge LinkedList|
In this article let’s see another approaches which helps to brainstorm most of the MAANG interview problem. This is the most important approach which helps to solve the problem in log(n) or some times in n log(n) in some cases (sorting the linked list).
In this approach as the name suggest we we merge two linked list in log(m+n), where m and n are the length of the two linked list respectively.
Where to Use ?
👊When you are asked to sort the linked list.
👊When you are asked to merge two sorted linked list.
In this article, we solve a problem called sort the list which involves this approach which is quiet frequently asked in various big tech companies in their coding interview and you also get to know about the working of merge sort.
If you had read my earlier article you know that we always focus on thought process i.e what they asked us to do rather than directly getting into the solution part. Let’s continue that streak here also,
Let’s see what they asked us to, they give us with the head of the linked list and we have to sort the linked list in ascending order and return the head. Let’s take a example which is given in the leetcode,
Example:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
The problem is pretty straight forward where they asked us to sort the linked list. Our answer should be efficient i.e we have to use the algorithm with less time complexity. Before that let’s see the the time complexity of various sorting algorithm.
Ignore the bubble, insertion, selection sort since they are O(n²). If you are dealing with array use quicksort or heap sort. The optimal approach to sort the linked list is to use merge sort since it takes only n*log(n) time complexity.
Let’s solve this problem using merge sort,
This algorithm splits the array(or linked list) into 2 halves until the size of the array(it splits the resultant array again) becomes 1 which would take log(n) times and after splitting compare the values and swap them accordingly which would take n times so the time complexity becomes n*log(n) for this algorithm.
What to do:
👊Find the middle node of the linked list.
👊Split the linked list with the help of middle node recursively.
👊After splitting, compare the values and start giving link according to the sorting order(in our case ascending order).
How to do:
Finding the middle node:
I already explained to find the middle node in my earlier article, do read that article where I clearly traced the algorithm(Floyd’s algorithm).The link of that article CLICK HERE.
Splitting of linked list:
With the help of the middle node, split the array into two halves recursively. The intuition to use recursion is then when you able to breakdown the complex problem into smaller parts, go for recursion.
Here we are splitting the list again and again so we are going with recursion. Here the base condition to stop splitting is when the given head is null or the next of head is null(i.e in the case, when the list only contains 1 element).
Let’s trace the flow for splitting with the another example given in the leetcode,
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
I traced what happens in recursive calls while splitting in the below, please try out yourself with pen and paper to have the flow.
These problems are implementation problem, after drawing the below tree, see what we are doing , code that and that’s it we are done.
In each step we are finding the middle node and split the list with the pivot as the middle node. i.e
left=-1(head)
right=4(next node to the middle node)
Now break the connection between the middle and the next node of the middle by making the middle points to NULL.
Now left will contains -1 → 5 → 3 → NULL (since we broke the connection in last step) and right will contain 4 → 0 → NULL then recursively split the left and right until it becomes as a single node.
Compare two list and merge:
Start from the bottom to up and sort them in ascending order and store them in the new list. Since we are creating another list, the space complexity would be O(n) where n is the total number of nodes in the resultant list. I traced that comparison below,
In each comparison done between the left and right list of the recursion tree. Comparison should be done from bottom to up. In our case,
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Left subtree:
1st comparison will be between the -1 → NULL and 5 → NULL, the resultant new list will be -1 → 5 → NULL and this will be returned to the above call.
2nd comparison will be between the list -1 → 5 → NULL and 3 → NULL, the resultant new list will be -1 → 3 → 5 → NULL and this will be returned to the above call.
In the last stage the left subtree will be -1 → 3 → 5 →NULL.
Right subtree:
1st comparison will be between the 4 → NULL and 0 → NULL the resultant new list will be 0 → 4 → NULL.
In the last stage of the right subtree will be 0 → 4 → NULL
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Now compare the last stage of both left subtree and right subtree the resultant new list will be -1 → 0 → 3 → 4 → 5 → NULL and now return the head of the head of the new list i.e the address of the first node. In our case the head is the address of the -1. As you see, after each comparison , we are merging two sorted list.
If you want to visualize try out how recursive call works do with pen and paper or do visit this website where you can see what happens in every step, HOVER ME(but it only works for positive number).
The below is the complete solution of this problem,
In Java:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode*head){
struct ListNode* slow=head;
struct ListNode* fast=head->next;
while(fast!=NULL && fast->next!=NULL){
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
struct ListNode* merge(struct ListNode* list1, struct ListNode* list2) {
struct ListNode dummy;
struct ListNode* add=&dummy;
while(list1 && list2){
if(list1->val < list2->val){
add->next=list1;
list1=list1->next;
}
else{
add->next=list2;
list2=list2->next;
}
add=add->next;
}
if(list1){
add->next=list1;
}
else{
add->next=list2;
}
return dummy.next;
}
struct ListNode* sortList(struct ListNode* head) {
if(head==NULL||head->next==NULL){
return head;
}
struct ListNode* mid=middleNode(head);
struct ListNode* left=head;
struct ListNode* right=mid->next;
mid->next=NULL;
left=sortList(left);
right=sortList(right);
struct ListNode* ans=merge(left,right);
return ans;
}In C:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode*head){
struct ListNode* slow=head;
struct ListNode* fast=head->next;
while(fast!=NULL && fast->next!=NULL){
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
struct ListNode* merge(struct ListNode* list1, struct ListNode* list2) {
struct ListNode dummy;
struct ListNode* add=&dummy;
while(list1 && list2){
if(list1->val < list2->val){
add->next=list1;
list1=list1->next;
}
else{
add->next=list2;
list2=list2->next;
}
add=add->next;
}
if(list1){
add->next=list1;
}
else{
add->next=list2;
}
return dummy.next;
}
struct ListNode* sortList(struct ListNode* head) {
if(head==NULL||head->next==NULL){
return head;
}
struct ListNode* mid=middleNode(head);
struct ListNode* left=head;
struct ListNode* right=mid->next;
mid->next=NULL;
left=sortList(left);
right=sortList(right);
struct ListNode* ans=merge(left,right);
return ans;
}Try the above program and get to understand about the flow using the debug pointers. Try out another leetcode problem where you have to merge two sorted list(Which is one the part of the merge sort).
If you find any value in this article, consider FOLLOWING me! Thanks 😇
#LearnInPublic #HappyCoding
