链表中的递归

# 21. 合并两个有序链表 (opens new window)

方法一：递归

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;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

方法二：归并

class Solution {
    public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while(p1!=null && p2!=null){
            if(p1.val>p2.val){
                p.next = p2;
                p2 = p2.next;
            }else{
                p.next = p1;
                p1 = p1.next;
            }
            p = p.next;
        }
        if(p1!=null) p.next = p1;
        if(p2!=null) p.next = p2;
        return dummy.next;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

← 链表排序链表中分治→