题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。
数据范围
链表长度 [0,500]。
样例
输入：1->3->5 , 2->4->5
输出：1->2->3->4->5->5
解法1：
public ListNode merge(ListNode l1, ListNode l2) {
if(l1==null||l2==null)return l1==null?l2:l1;//判断是否为空
ListNode head=null;
ListNode n1=l1;
ListNode n2=l2;
//将值最小的作为头结点
if(n1.val<=n2.val) {
head=n1;
n1=n1.next;
}
else {
head=n2;
n2=n2.next;
}
ListNode p=head;//尾指针,指向最后一个结点
while(n1!=null&&n2!=null) {
if(n1.val<=n2.val) {
p.next=n1;
n1=n1.next;
p=p.next;
}else {
p.next=n2;
n2=n2.next;
p=p.next;
}
}
//将剩余结点加入链表
while(n1!=null) {
p.next=n1;
n1=n1.next;
p=p.next;
}
while(n2!=null) {
p.next=n2;
n2=n2.next;
p=p.next;
}
return head;
解法2：递归思想
public ListNode dfMerge(ListNode l1, ListNode l2) {
if(l1==null||l2==null)return l1==null?l2:l1;//判断是否为空
ListNode res=dfMergeFun(l1, l2);
return res;
}
public ListNode dfMergeFun(ListNode l1, ListNode l2) {
if(l1==null||l2==null)return l1==null?l2:l1;//判断是否为空
ListNode temp=null;
if(l1.val<=l2.val) {
temp=l1;
temp.next=dfMergeFun(l1.next, l2);
}else {
temp=l2;
temp.next=dfMergeFun(l1, l2.next);
}
return temp;