## 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

```package algorithm.linkedlist;

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

```package algorithm.linkedlist;

}

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.

```package algorithm.linkedlist;

public class TwoSortedList {

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

Now Test the algorithm by writing a main method.

```package algorithm.linkedlist;

public class Test {

public static void main(String[] args) {

TwoSortedList twoSortedList = new TwoSortedList();
}
}
```

Use the LinkedListUtil class to print the sorted list.

```package algorithm.linkedlist;

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 ALGORITHM MICROSOFT