面试题25_合并两个排序的链表.md

面试题 25 ：合并两个排序的链表

---

leetcode-cn 题目地址

📗difficulty：Easy

🎯Tags：

• 链表

---

1. 题目描述📃

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

样例 1 ：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

• 0 <= 链表长度 <= 1000

注意：

• 本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/

---

2. 解题思路💡

思路分析

易错点：

• 没有考虑好合并的过程，导致合并的过程中，链表的中间断开了，或者出现合并后的链表并没有做到按递增排序。
• 代码鲁棒性的问题，一旦出现空指针输入就会导致崩溃。

处理指针问题，常用技巧。dummyHead 在这里也适用。

最后需要注意的是，需要注意一个链表走完，还剩下一个链表的情况。题目给定的链表都是递增的，将剩下的链表接上去即可。

代码实现

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode p1 = l1;
    ListNode p2 = l2;
    ListNode res = new ListNode(-1);
    ListNode cursor = res;
    while (p1 != null && p2 != null) {
        if (p2.val >= p1.val) {
            cursor.next = p1;
            p1 = p1.next;
        } else {
            cursor.next = p2;
            p2 = p2.next;
        }
        cursor = cursor.next;
    }

    // 处理其中还有链表存在剩余的情况
    cursor.next = (p1 != null ? p1 : p2);
    return res.next;
}

复杂度分析

• 时间复杂度：O(n) 。
• 空间复杂度：O(1) 。

以下思路来自 leetcode-cn 用户 腐烂的橘子 的题解，感谢其的详细分析。

递归算法

分 2 步走：

• 递归停止的条件（写递归第一个考虑的问题）：有一个链表为空。

• 如果递归：判断 l1.val 和 l2.val 谁更小。将较小的结点的 next 指针指向其余节点的结果。

代码实现

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null || l2 == null) {
        return l1 == null ? l2 : l1;
    } else {
        if (l1.val >= l2.val) {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        } else {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
    }
}

复杂度分析

• 时间复杂度：O(m + n) 。
• 空间复杂度：O(m + n) 。m 为 l1 的大小，n 为 l2 的大小。

---

3. 总结🎯

相似题目

21. 合并两个有序链表