剑指 Offer 25. 合并两个排序的链表

https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

思路一：迭代

同时遍历两个链表，比较两个链表当前的元素，将较小的元素添加到新的链表中，同时移动较小元素所在链表的指针；最后如果哪个链表不为空，直接将该链表上面剩余的元素全部连接到新的链表上面

class Solution {
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
        ListNode dummy=new ListNode();
        ListNode cur=dummy;
        while(l1!=null&&l2!=null){
    
            if(l1.val<l2.val){
    
                cur.next=l1;
                l1=l1.next;
            }else{
    
                cur.next=l2;
                l2=l2.next;
            }
            cur=cur.next;
        }
        if(l1!=null){
    
            cur.next=l1;
        }
        if(l2!=null){
    
            cur.next=l2;
        }
        return dummy.next;
    }
}
//O(n)
//O(1)

思路二：递归

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);
            return l1;
        }else{
    
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}
//O(n)
//O(n)