剑指 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

思路二：递归

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19