# 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);
}
}

public class LinkedList {

public LinkedList(Node node) {
}

public void add(Node node) {
Node temp = head;
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 {

public Node merge(Node<Integer> head1, Node<Integer> head2) {
if (head1 == null)
if (head2 == null)
Node head = new Node(0);
Node current = head;
while (head1 != null && head2 != null) {
} else {
}
current = current.next;
}
if (head1 != null) {
} else if (head2 != null) {
}
}
}

Now Test the algorithm by writing a main method.

public class Test {

public static void main(String[] args) {
Node head = new Node(1);

Node head1 = new Node(2);

TwoSortedList twoSortedList = new TwoSortedList();
}
}

Use the LinkedListUtil class to print the sorted list.

public class LinkedListUtil {

public static void print(Node head) {
Node temp = 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]