17. 合并两个有序链表：将两个升序的链表合并为一个新的升序链表

PangHu大约 4 分钟

要将两个升序的链表合并为一个新的升序链表，可以使用迭代或递归的方法。这是一道经典的链表操作题目，目的是将两个已经排序的链表合并成一个同样有序的链表。

链表节点的定义

首先，我们需要定义一个链表节点的类：

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

一、迭代法合并两个有序链表

1. 思路

迭代方法的基本思路是使用两个指针分别遍历两个链表，将较小的节点添加到结果链表中，并移动指针到下一个节点，直到两个链表都被遍历完。最后，将剩余的节点连接到结果链表的末尾。

2. 代码实现

public class MergeTwoSortedLists {

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个哑节点作为新链表的起点
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // 遍历两个链表，直到其中一个为空
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1; // 将 l1 的节点接入新链表
                l1 = l1.next; // 移动 l1 指针到下一个节点
            } else {
                current.next = l2; // 将 l2 的节点接入新链表
                l2 = l2.next; // 移动 l2 指针到下一个节点
            }
            current = current.next; // 移动新链表的指针
        }

        // 将剩余的节点（如果有）接入新链表
        if (l1 != null) {
            current.next = l1;
        } else if (l2 != null) {
            current.next = l2;
        }

        // 返回哑节点的下一个节点作为新链表的头节点
        return dummy.next;
    }

    public static void main(String[] args) {
        // 创建第一个有序链表：1 -> 2 -> 4
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);

        // 创建第二个有序链表：1 -> 3 -> 4
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);

        // 合并两个有序链表
        ListNode mergedHead = mergeTwoLists(l1, l2);

        // 打印合并后的链表
        while (mergedHead != null) {
            System.out.print(mergedHead.val + " ");
            mergedHead = mergedHead.next;
        }
    }
}

3. 时间复杂度和空间复杂度

时间复杂度：O(n + m)，其中 n 和 m 是两个链表的长度。每个节点被访问一次。
空间复杂度：O(1)，只使用了常数级别的额外空间。

二、递归法合并两个有序链表

1. 思路

递归方法的基本思想是将两个链表头部较小的节点与剩余部分的合并结果递归连接起来。具体步骤如下：

比较两个链表的当前节点值，选择较小的节点作为新链表的当前节点。
对剩余部分递归合并，将结果连接到新链表的当前节点后面。

2. 代码实现

public class MergeTwoSortedListsRecursive {

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 基本情况：当其中一个链表为空时，返回另一个链表
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }

        // 递归合并
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2); // l1 较小，继续合并 l1 的下一个节点
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next); // l2 较小，继续合并 l2 的下一个节点
            return l2;
        }
    }

    public static void main(String[] args) {
        // 创建第一个有序链表：1 -> 2 -> 4
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);

        // 创建第二个有序链表：1 -> 3 -> 4
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);

        // 合并两个有序链表
        ListNode mergedHead = mergeTwoLists(l1, l2);

        // 打印合并后的链表
        while (mergedHead != null) {
            System.out.print(mergedHead.val + " ");
            mergedHead = mergedHead.next;
        }
    }
}

3. 时间复杂度和空间复杂度

时间复杂度：O(n + m)，其中 n 和 m 是两个链表的长度。每个节点被访问一次。
空间复杂度：O(n + m)，由于递归调用的栈深度为 n + m，因此空间复杂度为 O(n + m)。

三、总结

迭代法：通过使用一个哑节点和迭代器，迭代方法能够高效地合并两个有序链表。时间复杂度为 O(n + m)，空间复杂度为 O(1)。适合在内存资源有限的情况下使用。
递归法：递归方法实现简洁、直观，但其空间复杂度为 O(n + m)，因为递归调用需要额外的栈空间。在链表较短时，递归方法是一种非常优雅的解决方案；在链表较长时，可能会导致栈溢出问题。

根据具体需求和资源条件，可以选择合适的方法来合并两个有序链表。