If you are preparing for the technical interview then this article is going to help you alot. If you have appeared in the technical interview before you must know that interviewer often ask questions from linked list. Today in this article we will see how to merge two sorted array in the linked list. Please read this article carefully .
Input : a = 2 -> 8 -> 15 -> 20 -> 30 , b = 5 -> 12 -> 22 -> 28
Output : 2 -> 5 -> 8 -> 12 -> 15 -> 20 -> 22 -> 28 -> 30
Input : a = 10 -> 20 -> 30 , b = 5 -> 25
Output : 5 -> 10 -> 20 -> 25 -> 30
Input : a = 20 -> 30 , b = null
Output : 20 -> 30
Java Code :
class Node{
int data;
NOde next;
Node(int data){
this.data=data;
this.next=null;
}
}
class HindiCodingCommunity{
public static Node SortedMerge(Node a,Node b){
if(a==null){return b;}
if(b==null){return a;}
Node head=null;
Node tail=null;
if(a.data<=b.data){
head=a;
tail=a;
a=a.next;
}
else{
head=b;
tail=b;
b=b.next;
}
while(a!=null && b!=null){
if(a.data<=b.data){
tail.next=a;
tail=a;
a=a.next;
}
else{
tail.next=b;
tail=b;
b=b.next;
}
}
if(a==null){tail.next=b;}
else{tail.next=a;}
return head;
}
public static void print(Node head){
Node curr=head;
while(curr!=null){
System.out.println(curr.data);
curr=curr.next;
}
}
public static void main(String args[])
{
Node head1= new Node(10);
head1.next= new Node(20);
head1.next.next = new Node(30);
head1.next.next.next = new Node(40);
Node head2= new Node(5);
head2.next= new Node(15);
head2.next.next = new Node(25);
head2.next.next.next = new Node(35);
Node sorted= SortedMerge(Node head1, Node head2);
System.out.println(sorted);
}
}
Time Complexity : O(m+n) : m is length of linked list-1 and n is the length of linked list-2
Space Complexity : O(1)
