合并两个升序链表

在之前我们说过，链表和二叉树这种数据结构类型的东西，基本上都可以使用递归来进行编写。

解题

题意已经很清晰了，我们来看看怎么使用递归进行解题。

1
2
3
4
5


class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
    }
}

首先，对于链表中的元素来说，合并完应该还是有序的，所以在合并的过程中就要求我们先放小的元素，再放大的元素，并且合并过之后的就是按照升序排列好的。

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


class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val < list2.val) {
            // 先放list1
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            // 放list2
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}