Linked Lists - A Concise and Practical Introduction to Programming Algorithms in Java - page 158

public static void main( String [ ] args )
{ List u= new List (8, null );u=u. insert(6);u=u. insert(3);
u.Display() ;
List v= new List (9, null );v=v.insert(7);v=v.insert(5);v=v.
insert (4) ;v=v. insert (2) ;
v.Display();
}
The easy case for merging lists is whenever one of the lists is empty (meaning
that either u or v is equal to null ). Indeed, in that case, we simply return the
other list (which might also be empty, in which case, both lists are empty).
Otherwise, both lists are considered non-empty, and we compare their head
elements u.container and v.container . Assume without loss of generality that
the integer of u.container is less than v.container . Then we need to set the
reference to the next field of u to the result of merging the two ordered lists
with heads referenced by u.next and v . That is where recursion beautifully kicks
in. Of course, in case u.container > =v.container we do the converse. Hence, the
recursive function for merging two ordered lists is quite simple as shown below:
Program 7.16 Merging two ordered linked lists
static List mergeRec(List u, List v)
if (u== null ) return v; // terminal case
if (v== null ) return u; // terminal case
// Recursion
if (u. container < v. container)
u.next=mergeRec(u.next ,v);
return u;
else
v. next=mergeRec(u,v. next) ;
return v;
}
}
7.6.2 Recursive sorting of lists
Now consider sorting any arbitrary linked list using the above recursive merging
procedure. The sorting algorithm will not create any new cells but rather set
the next field of every cell to the appropriate reference for linking appropriately
to the next cell.
We consider the following recursive sorting scheme: Split the initial list u in