static SNode mergeSortedList(SNode head1, SNode head2){
if(head1 == null)
return head2;
if(head2 == null)
return head1;
SNode curr1 = head1;
SNode curr2 = head2;
SNode curr = null;
SNode head = null;
while(curr1 != null || curr2 != null){
if(curr1 == null){
if(curr != null)
curr.next = new SNode(curr2.data);
else
head = curr = new SNode(curr2.data);
curr2 = curr2.next;
}else if(curr2 == null){
if(curr != null)
curr.next = new SNode(curr1.data);
else
head = curr = new SNode(curr1.data);
curr1 = curr1.next;
}else{
if(curr1.data < curr2.data){
if(curr == null){
head = curr = new SNode(curr1.data);
}else{
curr.next = new SNode(curr1.data);
}
curr1 = curr1.next;
}else{
if(curr == null)
head = curr = new SNode(curr2.data);
else{
curr.next = new SNode(curr2.data);
}
curr2 = curr2.next;
}
}
if(curr.next != null)
curr = curr.next;
}
return head;
}