Merge two sorted Linked Lists

Code: Merge Two Sorted LL
Send Feedback

You have been given two sorted(in ascending order) singly linked lists of integers.

Write a function to merge them in such a way that the resulting singly linked list is also sorted(in ascending order) and return the new head to the list.

Note :
Try solving this in O(1) auxiliary space.

No need to print the list, it has already been taken care.
Input format :
The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case or query contains the elements of the first sorted singly linked list separated by a single space. 

The second line of the input contains the elements of the second sorted singly linked list separated by a single space.
Remember/Consider :
While specifying the list elements for input, -1 indicates the end of the singly linked list and hence, would never be a list element
Output :
For each test case/query, print the resulting sorted singly linked list, separated by a single space.

Output for every test case will be printed in a seperate line.
Constraints :
1 <= t = 10^2
0 <= N <= 10 ^ 4
0 <= M <= 10 ^ 4
Where N and M denote the sizes of the singly linked lists. 

Time Limit: 1sec
Sample Input 1 :
1
2 5 8 12 -1
3 6 9 -1
Sample Output 1 :
2 3 5 6 8 9 12
Sample Input 2 :
2
2 5 8 12 -1
3 6 9 -1
10 40 60 60 80 -1
10 20 30 40 50 60 90 100 -1
Sample Output 2 :
2 3 5 6 8 9 12 
10 10 20 30 40 40 50 60 60 60 80 90 100


/****************************************************************

 

    Following is the class structure of the Node class:


        class Node

        {

        public:

        int data;

        Node *next;

        Node(int data)

        {

        this->data = data;

        this->next = NULL;

        }

        };


*****************************************************************/

void display(Node* head){


    Node* temp=head;


    while(temp!=NULL){


        cout<<temp->data<<" ";


        temp=temp->next;


    }

}

    


    






#include <bits/stdc++.h>

Node *mergeTwoSortedLinkedLists(Node *head1, Node *head2)

{

    //Write your code here

    if (head1==NULL and head2==NULL){

        return head1;

        

    }

    

    if (head1==NULL){

        return head2;

    }

    if(head2==NULL){

        return head1;

    }

    if (head1->data>head2->data){

        swap(head1,head2);

        

    }

    // display(head1);

    // display(head2);

    

    

    Node*ft=head1;

    Node*fh=head1;

    Node* temp=head1;

    Node* temp1=head1;

    Node* temp2=head2;

    temp1=temp1->next;

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

    if(temp1->data<=temp2->data){

            ft->next=temp1;

            ft=temp1;

            temp1=temp1->next;

        }

        else

        

            {

            ft->next=temp2;

            ft=temp2;

            temp2=temp2->next;

        }

        

        

        

    }

    if (temp1!=NULL){

            ft->next=temp1;

           // ft=temp1;

        }

if (temp2!=NULL){

            ft->next=temp2;

           // ft=temp2;

        }

    return fh;

    

    

    

    

    

    

}

Comments

Post a Comment

Popular posts from this blog

Sum of Even Numbers till N

Given a number N, print sum of all even numbers from 1 to N. #include<iostream> using namespace std; int main(){        /*  Read input as specified in the question. * Print output as specified in the question. */     int sum,n;     cin>>n;     sum=0;     for (int i=1;i<=n;i++){         if (i%2==0){             sum=sum+i;         }     }     cout<<sum;    } ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// #include<iostream> using namespace std; int main(){        /*  Read input as specified in the question. * Print output as specified in the question. */     int sum,n;     cin>>n;     sum=0;     for (int i=1;i<=n;i++){     ...
Read more

Find the Runner-Up Score!

  Given the participants' score sheet for your University Sports Day, you are required to find the runner-up score. You are given     scores. Store them in a list and find the score of the runner-up. Input Format The first line contains  . The second line contains an array     of   integers each separated by a space. Constraints Output Format Print the runner-up score. Sample Input 0 5 2 3 6 6 5 Sample Output 0 5 Explanation 0 Given list is  . The maximum score is  , second maximum is  . Hence, we print   as the runner-up score. ### OPTIMIZED ### from   collections   import   Counter if  __ name__  ==  '__main__' :      n  =  int ( input ())      arr  =  map ( int ,   input () . split ())           lis = list ( Counter ( arr ) . keys ())      lis . sort ()  ...
Read more

Print All Substrings

  For a given input string(str), write a function to print all the possible substrings. Substring A substring is a contiguous sequence of characters within a string. Example: "cod" is a substring of "coding". Whereas, "cdng" is not as the characters taken are not contiguous Input Format: The first and only line of input contains a string without any leading and trailing spaces. All the characters in the string would be in lower case. Output Format: Print the total number of substrings possible, where every substring is printed on a single line and hence the total number of output lines will be equal to the total number of substrings. Note: The order in which the substrings are printed, does not matter. Constraints: 0 <= N <= 10^6 Where N is the length of the input string. Time Limit: 1 second Sample Input 1: abc Sample Output 1: a ab abc b bc c  Sample Input 2: co Sample Output 2: c co o #include <iostream> #include <cstring> us...
Read more