【LeetCode】21. 合并两个有序链表(Java自用版)

递归：

以下是使用递归方式实现的完整Java代码，用于将两个升序链表合并为一个新的升序链表：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

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.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}
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
26

在 mergeTwoLists 方法中，我们使用了递归的方式来合并两个链表。首先，我们检查递归的终止条件：如果其中一个链表为空，我们直接返回另一个链表。然后，我们比较两个链表的头节点的值，将较小的节点作为新链表的头节点，并递归地合并剩余的部分。最后，我们返回合并后的新链表。

请注意，上述代码假设输入的链表 list1 和 list2 已经是升序排列的。如果输入的链表不是升序排列的，那么合并后的链表可能不是升序排列的。在实际应用中，你可能需要首先对链表进行排序，然后再使用上述代码进行合并。