（题目来源:力扣LeetCode)
题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
方法：递归法
class Solution {
public ListNode mergeTwoLists(ListNode L1, ListNode L2) {
//有空链表时，返回非空链表
//如果L1是空链表，直接输出L2
//如果L2是空链表，直接输出L1
//如果两链表都不为空，则比较L1和L2链表的头节点的值，更小的在前，然后递归决定之后的下一个节点
//如果有一个为链表为空，递归结束
if(L1==null){
return L2;
}else if(L2 == null){
return L1;
}else if(L1.val<L2.val){
L1.next = mergeTwoLists(L1.next,L2);
return L1;
}
L2.next = mergeTwoLists(L1,L2.next);
return L2;
}
}
方法：迭代法
class Solution {
public ListNode mergeTwoLists(ListNode L1, ListNode L2) {
//设定一个哨兵节点prehead；
//设置一个调整指针prev放在prehead处；
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
//比较L1和L2当前的指针所指的节点值，选择小的那个接在prev指针的后面
//将L1或L2的指针向后移动一位
while(L1!=null && L2!=null){
if(L1.val<=L2.val){
prev.next=L1;
L1=L1.next;
}else{
prev.next=L2;
L2=L2.next;
}
//将prev指针后移一位，
prev=prev.next;
}
//之后再次比较两链表节点值的大小
//当有链表为空时
prev.next=L1==null ? L2:L1;
return prehead.next;
}
}
