Linked Lists - Advanced Topics in Java: Core Concepts in Data Structures - page 102

LinkedList C = new LinkedList();
while (A != null && B != null) {
if (A.data.compareTo(B.data) < 0) {
C.addTail(A.data);
A = A.next;
}
else {
C.addTail(B.data);
B = B.next;
}
}
while (A != null) {
C.addTail(A.data);
A = A.next;
}
while (B != null) {
C.addTail(B.data);
B = B.next;
}
return C;
} //end merge
As implemented, addTail has to traverse the entire list to find the end before adding each new node. This is
inefficient. We could keep a pointer ( tail , say) to the end of the list to facilitate adding a node at the end. But this
would complicate the class unnecessarily at this stage.
Since adding a node at the head is a simple, efficient operation, it would be better to add a new node at the head
and, when the merge is completed, reverse the list. We will modify merge by replacing addTail with addHead and, just
before return C , we insert the statement C.reverseList(); .
To test merge , we write Program P3.6. It requests the user to enter data for two lists. The data can be entered in
any order. The lists will be built in sorted order by adding each new number “in place.”
We remind you that this program requires the int version of the NodeData class, which is declared public and
stored in the file NodeData.java . It also requires that the function merge be put in the LinkedList class, which is
declared public and stored in the file LinkedList.java . Of course, Program P3.6 is stored in the file MergeLists.java .
Program P3.6
import java.util.*;
public class MergeLists {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
LinkedList A = createSortedList(in);
LinkedList B = createSortedList(in);
System.out.printf("\nWhen we merge\n");
A.printList();
System.out.printf("with\n");
B.printList();
System.out.printf("we get\n");
A.merge(B).printList();
} //end main