My Muri Life

切换主题

本页目录

其它链表篇 ​

倒数第K个节点 ​

剑指 Offer II 021. 删除链表的倒数第 n 个结点

双指针 ​

解题思路

声明快慢指针let [s, f] = [head, head]：

  • 先让快指针走k步，并判断此时的快指针是否为null：
    • 若为null，则说明k===len(len为链表表长)，即删除表头节点。
  • 再让快慢指针一起走，直到快指针到达链表尾节点，此时慢指针的下一节点即为待删除节点，删除节点即可。
JavaScript
const removeNthFromEnd = (head, k) => {
  let [s, f] = [head, head]
  while (k--) {
    f = f.next
  }
  // k === len 删除表头
  if (!f) return head.next
  while (f.next) {
    s = s.next
    f = f.next
  }
  s.next = s.next.next
  return head
}

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

展平多级双向链表 ​

剑指 Offer II 028. 展平多级双向链表

前序遍历 ​

解题思路

我们将其视为二叉树，若双项链表的某一节点node具有child，可等价转化为：

  • 将node视为根节点root；
  • 其child子双向链表视为根节点root的左子树；
  • 其next节点及其节点视为根节点root的右子树。

对于题中的要求即转换为二叉树的前序遍历。

JavaScript
const flatten = head => {
  let curr = null
  const dfs = node => {
    if (!node) return
    const { child, next } = node // root
    node.child = null
    node.next = null
    if (curr) {
      curr.next = node
      node.prev = curr
    }
    curr = node
    dfs(child) // 左子树
    dfs(next) // 右子树
  }
  dfs(head)
  return head
}

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

迭代法 ​

解题思路

为了简化处理，设置虚拟头节点dummy，然后遍历链表：

  • 当遍历到的节点child不为null时，先缓存其child节点和下一节点next；
  • 将当前节点与子节点连接，并将.child指针置为null；
  • 然后从当前节点last = head遍历子链表至其最后一个节点;
  • 将子链表的最后一个节点last与其父节点的next节点相连。

最后返回dummy.next。

JavaScript
const flatten = head => {
  const dummy = new Node(-1, null, head)
  // 遍历链表
  while (head) {
    // 处理子链表
    if (head.child) {
      // 缓存
      const [next, child] = [head.next, head.child]
      // 连接
      head.next = child
      child.prev = head
      // 处理过了，置空
      head.child = null
      // 遍历已连接的子链表
      let last = head
      while (last.next) last = last.next
      // 连接至父级层
      last.next = next
      if (next) next.prev = last
    }
    head = head.next
  }
  return dummy.next
}

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