题解 | #合并两个排序的链表#

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
/*****************迭代--非递归，二路合并******************/
//         if(list1 == null)
//             return list2;
//         if(list2 == null)
//             return list1;
//         ListNode dummy = new ListNode(-1);
//         ListNode cur = dummy;
//         //循环遍历两个连表，两个链表不为空循环合并
//         while(list1 !=null && list2 != null){
//             if(list1.val < list2.val){
//                 cur.next = list1;
//                 list1 = list1.next;
//             }else{
//                 cur.next = list2;
//                 list2 = list2.next;
//             }
//             //后移指针
//             cur = cur.next;
//         }
//         //判断list1是空还是list2，将非空的连接到结果集上
//         cur.next = list1 != null ? list1 : list2;
//         return dummy.next;
/**************************递归写法************************/
        
        //递归终止条件
        if(list1 == null)
            return list2;
        else if (list2 == null)
            return list1;
        
        //递归部分
        else if(list1.val < list2.val){
            //将其指向剩下部分中较小的
            list1.next = Merge(list1.next,list2);
            //回溯返回,已经连接好的list1以及其后半部分
            return list1;
        }
        else{
            list2.next = Merge(list1,list2.next);
            return list2;
        }
    }
}