If we have two sorted linked list and we want to merge both in a new list without creating new node space then we can use recursive approach for this . This approach takes O(max(m,n)) time complexity for merging.
Like we have a linked list named : list 1 1 -> 2 -> 3 -> 4
and another list named : list2 5 -> 6 -> 7
then resulting linked list will be 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
here is an coding example for merge operation :
public Node<T> mergeLinkedList(Node<T> list1, Node<T> list2)
{
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
if(list1.getValue() < list2.getValue()){
list1.next = mergeLinkedList(list1.next , list2);
return list1;
}else{
list2.next = mergeLinkedList(list2.next , list1);
return list2;
}
}
0 Comment(s)