长春建站培训班汽车网站建设方案预算

LeetCode 21. 合并两个有序链表

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接两个链表的节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数在范围 [0, 50] 内
• 0 <= Node.val <= 1000
• 列表中的每个节点都有一个唯一的 val 值

Java 实现解法

方法一：递归

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {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;}}
}

方法二：迭代

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null)return l2;if (l2 == null)return l1;ListNode dummy = new ListNode(0);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;}
}

解题思路

• 递归方法：

  • 递归的基本情况是当链表 l1 或 l2 为 null 时，直接返回另一个链表。
  • 在递归过程中，比较两个链表头节点的值，将较小的节点链接到结果链表中，然后递归地合并下一个节点和另一个链表的剩余部分。

• 迭代方法：

  • 创建一个虚拟头节点 dummy，用于简化插入操作。
  • 使用一个 while 循环，当两个链表都非空时，比较两个头节点的值，将较小的节点链接到 curr 后面，并移动对应的链表指针。
  • 更新 curr 指针，指向新链接的节点。
  • 当一个链表为空时，将另一个链表的剩余部分链接到 curr 后面。

这两种方法的时间复杂度都是 O(n + m)，其中 n 和 m 分别是链表 l1 和 l2 的长度。空间复杂度对于递归方法是 O(n + m)，因为递归栈的深度最多为两个链表长度之和；对于迭代方法是 O(1)，因为我们只使用了有限的额外空间来存储指针。迭代方法通常更受青睐，因为它避免了递归可能引起的栈溢出问题。