Java有序链表怎么合并

合并两个有序链表是一个经典的问题。当我们想要把两个有序链表合并成一个有序链表时，可以使用迭代或递归的方法。本文将使用Java语言解答这个问题。

方法一：迭代

首先，我们创建一个新的链表，用来保存合并后的结果。然后我们同时遍历两个链表，比较两个链表当前节点的值，将较小的值添加到新链表中，并将指针后移一位。重复这个过程直到其中一个链表为空。最后将非空链表的剩余部分直接添加到新链表的末尾。

下面是具体的代码实现：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 创建一个新的链表，用来保存合并后的结果
    ListNode dummy = new ListNode(-1);
    ListNode curr = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    
    // 将非空链表的剩余部分直接添加到新链表的末尾
    curr.next = (l1 != null) ? l1 : l2;
    
    return dummy.next;
}

方法二：递归

使用递归的方法合并有序链表相对简洁一些。我们可以通过递归地合并链表的子链表，然后将较小的头节点添加到结果链表中。

下面是具体的代码实现：

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

总结

以上就是使用Java语言合并有序链表的两种方法：迭代和递归。迭代的方法比较直观，通过比较当前节点的值来不断添加较小的节点到新链表中。递归的方法更为简洁，通过递归地合并链表的子链表和比较头节点的值来完成合并。选择哪种方法取决于个人的喜好和具体的应用场景。

无论使用哪种方法，合并两个有序链表的时间复杂度都是O(m+n)，其中m和n分别是两个链表的长度。空间复杂度是O(m+n)，需要额外的空间保存合并后的链表。