Merge Two Sorted Linked List Geeks For Geeks

 Problem Link:

https://practice.geeksforgeeks.org/problems/merge-two-sorted-linked-lists/1#

(It is also the problem of the day for 07-05-2022)

Solution:

class LinkedList

{

    Node sortedMerge(Node head1, Node head2) {

        Node temp1=head1;

        Node temp2=head2;

        Node temp3=new Node(-1);

        Node temp4=temp3;

        

        while(temp1!=null && temp2!=null){

            if(temp1.data<=temp2.data){

                temp3.next=new Node(temp1.data);

                temp3=temp3.next;

                temp1=temp1.next;

                

            }

            else{

                temp3.next=new Node(temp2.data);

                temp3=temp3.next;

                temp2=temp2.next;

            }

               

               

        }

        

        while(temp1!=null){

            temp3.next=new Node(temp1.data);

            temp1=temp1.next;

             temp3=temp3.next;

        }

        

         while(temp2!=null){

            temp3.next=new Node(temp2.data);

            temp2=temp2.next;

            temp3=temp3.next;

        }

        

        return temp4.next;

    }

    

}

Time Complexity: O(N+M)[GFG Time:3.61/7.49]

Space Complexity: O(N+M)[Lnked LIsts are given]

Auxiliary Space: O(N+M)[A third linked list is created]

Total Test Cases:303

Approach Used:

1.Traverse both linked list simultaneosuly and see which value is smaller.

ex: 

if linked list 1 ie l1 is ={2,5,7}

linked list l2 is={1,3,4,8}   

linked list l3={}

Consider temp1->l1

temp2->l2

temp3->l3

then start traversal till one list completes ie the small size list.

Here it is list 1 as size 3 is small in comparison with size 4 of list 2.

So we start traversal and compare the first element of both the lists ie 1 and 2.

since 1<2 is present in list 2 we will append it in list 3 and move forward temp3 and temp2.

now temp1-> index 0 of l1(same as earlier)

temp2-> index 1 of l2

temp3={1}

Now next comparison will be between 2 and 3 and since 2 is smaller than 3 we will append it in list 3 and move forward with both temp3 and temp1 pointers.

temp1-> index 1 of l1

temp2-> index 1 of l2

temp3={1,2}

In the same way, we will traverse the whole linked list and keep on adding the nodes in linked list 3.

Now one thing to observe is that we have completed the traversal of one linked list only .

It means we have added the elements of the short linked list only in the newly created linked list. while for the leftover elements of the bigger linked list, we want to traverse them separately and keep on adding them to the new list.

Here in reference:

list 1 will be fully traversed while some elements of list 2 will be left untraversed. so for that, we will run a separate loop and add them to list 3.

Finally, we will get our linked list sorted and merged and we will return it.

{

    Since we formed a new list with temp3 it will look like

    {-1,1,2,3,4,5,7,8}

    This -1 will appear at the start as initially, we created list3 with a new node -1.

    So to remove this -1 from start we will have temp4.next where temp4->temp3

    temp4-> index 0 of list 3 ie -1

    temp4.next-> index 1 of list 3 ie 1

    return temp4.next; 

}

"Thanks for Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"