My Muri Life

切换主题

本页目录

合并链表篇 ​

合并两个 ​

21. 合并两个有序链表

迭代法 ​

解题思路

设置虚拟头节点dummy：

  • 当l1和l2均不为空时，迭代比较当前节点值，小的节点插入表中，并更新新链表p = p.next；
  • 当l1或l2为空时，将非空表拼接在新链表后p.next = l1 == null ? l2 : l1，返回dummy.next。
JavaScript
const mergeTwoLists = (l1, l2) => {
  const dummy = new ListNode(-1)
  let p = dummy
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      p.next = l1
      l1 = l1.next
    } else {
      p.next = l2
      l2 = l2.next
    }
    // p 步进
    p = p.next
  }
  p.next = l1 ?? l2
  return dummy.next
}

时间复杂度：O(m+n)；空间复杂度：O(1)。

递归法 ​

JavaScript
const mergeTwoLists = (l1, l2) => {
  if (!l1) {
    return l2
  } else if (!l2) {
    return l1
  } else if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLists(l1, l2.next)
    return l2
  }
}

时间复杂度：O(m+n)；空间复杂度：O(1)。

合并K个 ​

23. 合并 K 个升序链表

顺序迭代法 ​

解题思路

在合并两个有序链表的基础上，按顺序迭代即可。

JavaScript
const mergeKLists = lists => {
  let newHead = null
  for (const l of lists) {
    newHead = mergeTwoLists(newHead, l)
  }
  return newHead
}

时间复杂度：O(n*k^2) K为数组长/N为单链表最长长度；空间复杂度：O(1)。

归并法 ​

解题思路

在合并两个有序链表的基础上，归并即可。

JavaScript
const merge = (list, l, r) => {
  if (l === r) return list[l]
  if (l > r) return null
  const mid = (l + r) >> 1
  return mergeTwoLists(merge(list, l, mid), merge(list, mid + 1, r))
}

const mergeKLists = lists => {
  const len = lists.length - 1
  return merge(lists, 0, len)
}

时间复杂度：O(knlogk) K为数组长/N为单链表最长长度；空间复杂度：O(logk)。