Merge two Sorted Linked List into a Third Linked List
Java program to Merge two sorted lists into a third list. Below program has, both a recursive and iterative version methods
public class MergeLinkList {
private Link mergeRecursive( Link l1, Link l2 ) {
if ( l1 == null) return l2;
if ( l2 == null ) return l1;
Link mergedhead = null;
if ( l1.value() < l2.value() ) {
mergedhead = l1;
mergedhead.next = mergeRecursive(l1.next, l2);
}else {
mergedhead = l2;
mergedhead.next = mergeRecursive(l1, l2.next);
}
return mergedhead;
}
private Link mergeInterative( Link l1, Link l2 ) {
if ( l1 == null) return l1;
if ( l2 == null ) return l2;
Link p1 = l1;
Link p2 = l2;
Link mergedHead= null;
Link last = mergedHead;
while ( p1!= null && p2 != null ) {
if ( p1.value() < p2.value() ) {
if ( last == null ) {
last = new Link(p1.value());
mergedHead = last;
}else {
last.next = new Link( p1.value());
last = last.next;
}
p1 = p1.next;
}else {
if ( last == null ) {
last = new Link(p2.value());
mergedHead = last;
}else {
last.next = new Link( p2.value());
last = last.next;
}
p2 = p2.next;
}
}
if ( p1 != null ) {
insertAll( p1, last );
}else
insertAll( p2, last );
return mergedHead;
}
private void insertAll( Link p1, Link last ) {
do {
last.next = new Link(p1.value());
p1 = p1.next;
}while ( p1 != null );
}
public static void main( String[] args ) {
/*
* .................n..........n.............n.........n.............n.......................n............n.......... ---> Number line for Array1, has 8 numbers in ascend
* .....n...n...........n......... n...n..........n.........n....................................................................
* */
int[] ar1 = new int[] { 45, 56, 77, 89, 150, 187, 198};
int len1 = 7;
int[] ar2 = new int[] { 23, 29, 47, 59, 67, 80, 106 };
int len2 = 7;
Link l1 = Link.build( ar1 );
Link l2 = Link.build(ar2);
MergeLinkList merge = new MergeLinkList();
Link mergedIter = merge.mergeInterative(l1, l2);
mergedIter.print(mergedIter);
System.out.println("Prining recursively");
Link mergedRecursive = merge.mergeRecursive(l1, l2);
mergedRecursive.print(mergedRecursive);
}
}
No comments:
Post a Comment