跳到主要内容

21. 合并两个有序链表

题目描述​

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

出处：LeetCode

解法一：递归​

思路​

我们可以使用递归来合并两个有序链表。我们定义一个递归函数 merge，用来合并两个有序链表。在递归函数中，我们首先判断两个链表是否为空，如果其中一个链表为空，则返回另一个链表。然后我们比较两个链表的头节点，将值较小的头节点作为新链表的头节点，然后递归地合并剩余的链表。

实现​

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  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;
  }
}

复杂度分析​

  • 时间复杂度：O(n+m)O(n + m)，其中 nn 和 mm 分别是两个链表的长度。
  • 空间复杂度：O(n+m)O(n + m)，递归调用的深度为 n+mn + m。

解法二：迭代​

思路​

我们也可以使用迭代来合并两个有序链表。我们定义一个哑节点 dummy，然后定义一个指针 prev 指向哑节点。然后我们遍历两个链表，每次迭代时，我们比较两个链表的头节点，将值较小的头节点加入到新链表中。最后，我们将剩余的链表加入到新链表的尾部。

实现​

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let prev = dummy;

  while (l1 !== null && l2 !== null) {
    if (l1.val < l2.val) {
      prev.next = l1;
      l1 = l1.next;
    } else {
      prev.next = l2;
      l2 = l2.next;
    }

    prev = prev.next;
  }

  prev.next = l1 !== null ? l1 : l2;

  return dummy.next;
}

复杂度分析​

  • 时间复杂度：O(n+m)O(n + m)，其中 nn 和 mm 分别是两个链表的长度。
  • 空间复杂度：O(1)O(1)