每日一练（剑指offer）合并二个排序的链表

描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

示例

输入：

{1,3,5},{2,4,6}

返回值：

{1,2,3,4,5,6}

代码如下（java）????????

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
// list1 list2为空的情况
if(list1==null||list2==null){
return list1!=null?list1:list2;
        }
//二个链表元素依次对比
if(list1.val<=list2.val){
//递归计算 list1.next,list2
list1.next=Merge(list1.next,list2);
return list1;
        }else{
//递归计算 list1,list2.next
list2.next=Merge(list1,list2.next);
return list2;
        }
    }
}