## Merge Two Sorted Linked Lists

Write a merge function that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order. The merge should return the new list. The new list should be made by splicing together the nodes of the first two lists. Following is the Linked NODE and LinkedList ADT we are going to use to solve the problem. For example if the first linked list is 5->10->15 and the other linked list is 2->3->20, then merge should return a pointer to the head node of the merged list 2->3->5->10->15->20.

Node.Java

public class Node<T> {

T data;
Node next;

public Node(T data) {
this.data = data;
this.next = null;
}

public void print() {
String printValue = "[ " + this.data + "] ";
if (next != null) {
printValue += "---> ";
}
System.out.print(printValue);
}
}

}

while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}
}

The merge method in TwoSortedList class is merging the two sorted list into a single sorted list. The strategy here uses a temporary dummy node as the start of the result list. The pointer Tail always points to the last node in the result list, so appending new nodes is easy.

public class TwoSortedList {

} else {
}
current = current.next;
}
} else if (head2 != null) {
}
}
}

Now Test the algorithm by writing a main method.

public class Test {

public static void main(String[] args) {

TwoSortedList twoSortedList = new TwoSortedList();
}
}

Use the LinkedListUtil class to print the sorted list.

public static void print(Node head) {
while (temp != null) {
temp.print();
temp = temp.next;
}
}

public static void newLine(){
System.out.println();
}
}

Output of the program is:

[ 1] ---> [ 2] ---> [ 3] ---> [ 4] ---> [ 5] ---> [ 6] ---> [ 7] ---> [ 8] ---> [ 9]

core java 12 Algorithm 12 Microsoft 12