Commonly asked Data Structures and Algorithms Problems by big tech and different solution approaches with code in Java and C

Powered by Blogger.

Monday, July 31, 2017

Merge Two Sorted LinkedList


Here we are going to perform merge in O(1) space complexity.

Idea :
i will use two variable 1 will points to head of LL and another to the LL having smaller value than the upcoming node , i.e. this will be used to link it's next to another node.

we will point variable to the list with smaller value and process the linking .

Code:


class gfg
{
    Node MergeLists(Node headA, Node headB) {
        Node head;
        Node start;
        if(headA==null)
        return headB;
        if(headB==null)
        return headA;
        if(headA.data<headB.data)
        {
            head=headA;
            headA=headA.next;
            //head
        }
       else
        {
            head=headB;
            headB=headB.next;
        }
        start=head;
        while(headA!=null && headB!=null)
        {
            if(headA.data<headB.data)
        {
            head.next=headA;
            head=head.next;
            headA=headA.next;
            //head
        }
       else 
        {
            head.next=headB;
            head=head.next;
            headB=headB.next;
        }
        }
         if(headA==null)
        head.next=headB;
        if(headB==null)
        head.next=headA;
   return start;
   } 
}

0 Comments:

Post a Comment

Stats