Merging two Sorted Linked List using java

Merge two linked list that are aleady sorted and return a new sorted list.

Implement this method :

1. Node MergeLists(Node list1, Node list2){
2. // your code here
3. }

Solution:

1. 
   
2. class Node{
3.     int data;
4.     Node next;
5. Node MergeLists(Node list1, Node list2) {
6.   if (list1 == null) return list2;
7.   if (list2 == null) return list1;
8. 
   
9.   if (list1.data < list2.data) {
10.     list1.next = MergeLists(list1.next, list2);
11.     return list1;
12.   } else {
13.     list2.next = MergeLists(list2.next, list1);
14.     return list2;
15.   }
16. }
17. }