Merging two Sorted Linked List | Easiest Explanation

 

Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example

Suppose, list1 refers to 1 --> 2 ---> 4 --->7 ---> NULL

Suppose, list2 refers to 1 --> 3 ---> 4 ---> NULL

The merged linked list should be 1-->1-->2--->3--->4--->4--->7--->NULL

Constraints

• The number of nodes in both lists range [0, 50].
• -100 <= Noda.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

How to code for it? [Step by step explanation]

Consider two linked lists list1 and list2 with data as shown in below image

Step 1) Make a new dummy node. (Why? You'll get to know later that why we are creating this dummy node).

Note: You can make dummy node with any data (value), I have used -1 during it's initialisation.

Step 2) Make three pointers which are pointing towards head of list1, list2 and dummy. I have named them as pt1, pt2 and pt3 respectively.

 Step 3) Compare the data of pt1 & pt2, one which is smaller will be added next to head of dummy node. And if both are equal then anyone can be added next to head of dummy. Here both pt1 & pt2 have equal values (i.e. 1) so add anyone nex to head of pt3. I am adding pt2.

Step 4) Then shift the pointer, which was added, to the next node. Here, since we have added pt2 in the previous step we will shift it to next node. Shift the pt3 to the next node. See the image below.

Step 5) Again compare the values of node pt1 and pt2, check which one is smaller, add the smaller next to pt3, shift the added pointer to next node and pt3 to next node. Here value of pt1 < value of pt2 (1<2), thus add pt1 node next to pt3 and shift pt1 by one node and pt3 by one node.

Step 6) Keep using step 5 until any pointer (either pt1 or pt2) reaches to null. As soon as any pointer reaches null the condition will be as below: 

Note that since list1 was smaller in length than list2 that's why pt1 first reached to NULL but any of the pointer t.e. either pt1 or pt2 can reach null.

So after this we will add all other nodes of the pointer which is not null in the end of pt3. Here pt2 is not yet null so we will add remaining elements in the end of pt3.

So finally our result will be: 

Please note that you'll have to return dummy->next instead of dummy because our merged list is starting from 2nd node of dummy (not from 1st node).

Implementation in C:

SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    
    SinglyLinkedListNode* dummy = malloc(sizeof(SinglyLinkedListNode));
    dummy->data = -1;
    dummy->next = NULL;
    
    SinglyLinkedListNode* pt1 = head1;
    SinglyLinkedListNode* pt2 = head2;
    SinglyLinkedListNode* pt3 = dummy;
    
    while (pt1!=NULL && pt2!=NULL) {
        if (pt1->data>pt2->data) {
            pt3->next=pt2;
            pt2=pt2->next;
        }
        else {
            pt3->next=pt1;
            pt1=pt1->next;
        }
        pt3=pt3->next;
    }
     while (pt1!=NULL) {
        pt3->next=pt1;
        pt1=pt1->next;
        pt3=pt3->next;
    }
    while (pt2!=NULL) {
        pt3->next=pt2;
        pt2=pt2->next;
        pt3=pt3->next;
    }
    
    return dummy->next;

}

Implementation in Java:

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
        ListNode dummy = new ListNode(-1);
        
        ListNode pt1 = list1;
        ListNode pt2 = list2;
        ListNode pt3 = dummy;
        
        while(pt1!=null && pt2!=null){
            if(pt1.val<pt2.val){
                pt3.next=pt1;
                pt1=pt1.next;
            }
            else{
                pt3.next=pt2;
                pt2=pt2.next;
            }
            pt3=pt3.next;
        }
        while(pt1!=null){
            pt3.next=pt1;
            pt1=pt1.next;
            pt3=pt3.next;
        }
        while(pt2!=null){
            pt3.next=pt2;
            pt2=pt2.next;
            pt3=pt3.next;
        }
        return dummy.next;
        
    }
}

Thank you Readers for being with me till end of this blog. I'll see you in the next blog with more useful contents till then keep learning. :)

Labels : #c program ,#java program ,#linked list ,