[数据结构与算法]合并两个有序链表

题目来源：
leetcode：合并两个有序链表

老规矩，这一题呢还是有两种思路，但是第二种递归确实不好想。

第一种：创建新链表

就是创建一个新的链表，然后把两个链表每个节点的value值进行比较，谁小连谁，直到其中一方为空时候停止，然后把另一条链表剩下的所有补上去。
具体代码如下：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode list = new ListNode();
        ListNode key = list;
        //现在开始合并
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                key.next = l1;
                l1 = l1.next;
                key = key.next;
            }else{
                key.next = l2;
                l2 = l2.next;
                key = key.next;
            }
        }
        //总会有一个先到头，那么这个时候就把另外一条链表直接连在后面
        if(l1 == null){
            key.next = l2;
        }else{
            key.next = l1;
        }
        //如果返回list形式就是错了，因为我并没有给list第一个节点赋值。
        return list.next;
    }
}

第二种：递归

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    	//确定临界条件为不等于null
        if(l1 == null){return l2;}
        if(l2 == null){return l1;}
		//那一个小，递归调用时候传的就是谁的next，另外一个不动
        if(l1.val > l2.val){
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
        l1.next = mergeTwoLists(l1.next,l2);
        return l1;
    }
}