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;
}
}
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