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

3.15 Merging Two Sorted Linked Lists
In Section 1.10, we considered the problem of merging two ordered lists. There, we showed how to solve the problem
when the lists were stored in arrays. We now will show how to solve the same problem when the lists are stored as
linked lists. We consider the problem of merging two ordered linked lists to produce one ordered list.
Suppose the given lists are as follows:

A

21 28 35 40 61 75

and

B

16 25 47 54

We want to create one linked list with all the numbers in ascending order, thus:

C

16 21 25 28 35 40 47 54 61 75

We will create the merged list by creating a new node for each number that we add to list C ; we leave lists A and B
untouched. We will use the same algorithm that we used in Section 1.10. Here it is for easy reference:

while (at least one number remains in both A and B) {
if (smallest in A < smallest in B)
add smallest in A to C
move on to next number in A
else
add smallest in B to C
move on to next number in B
endif
}
//at this stage, at least one of the lists has ended
while (A has numbers) {
add smallest in A to C
move on to next number in A
}
while (B has numbers) {
add smallest in B to C
move on to next number in B
}

Since our lists contain integers, we will have to use the int version of NodeData .
If A and B are of type LinkedList , we will write an instance method, merge , in the LinkedList class such that
A.merge(B) will return a LinkedList containing the merged elements of A and B . Here is merge :

public LinkedList merge(LinkedList LL) {
Node A = this.head;
Node B = LL.head;