题目分析

合并两个有序链表是一个常见的算法问题，要求将两个升序链表合并为一个新的升序链表并返回。

这个问题可以通过迭代法解决。

解题思路

哨兵节点(dummy)：无论合并过程如何进行，哨兵节点始终指向新链表的头部；
迭代：通过迭代遍历两个链表，每次比较两个链表当前节点的值，选择较小值的节点接到当前节点(current)的后面，然后移动所选节点的链表指针(l1或l2)和current指针；
合并剩余部分：一旦一个链表先遍历完，将另一个链表的剩余部分直接接到当前节点的后面。

Java解法

下面是使用Java语言的解法：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建哨兵节点
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

        // 遍历两个链表，直到一个达到末尾
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // 处理剩余节点
        current.next = l1 == null ? l2 : l1;

        return dummy.next;
    }
}

时间复杂度

时间复杂度主要取决于两个链表的长度。在合并过程中，每个元素都会被访问和比较一次，直到所有元素都被合并到结果链表中。因此，如果两个链表的长度分别为 n 和 m，那么算法的时间复杂度为 O(n + m)。这表示算法的运行时间与两个链表的总长度线性相关。

空间复杂度

迭代解法的空间复杂度主要由额外使用的变量（如哨兵节点和一些临时变量）决定，它们的数量与输入的链表长度无关，因此是常数级别的。所以，算法的空间复杂度为 O(1)。这意味着算法的空间消耗不随输入数据的大小而变化，仅使用了固定的额外空间。

References

21. 合并两个有序链表 ↩︎

趣味算法题