leetcode21. 合并两个有序链表

1.题目描述：

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

 2.普通解法：遍历输入的两个链表，比较val值的大小，直接见代码。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        ListNode temp1 = list1;
        ListNode temp2 = list2;
        ListNode resNode = new ListNode(-1);//初始化一个头节点防止空指针
        ListNode temp = resNode;
        while(temp1 != null && temp2 != null){ 
            if(temp1.val <= temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            }else{
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        temp.next = temp1 == null ? temp2 : temp1;//其一遍历完后直接拼接另一
        return resNode.next;
    }
}

3.递归：直接想代码很困难，根据代码走一遍示例依次返回443211并往前拼接，自己走一遍即可图解略。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);//比较当前l1后一个节点与当前l2大小
            return l1;//回溯时拼接成非递减链表
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}