My Muri Life

切换主题

本页目录

复制链表篇 ​

深拷贝链表 ​

实现很简单：

JavaScript
const copyList = head => {
  const dummy = new ListNode(-1)
  let [prev, curr] = [dummy, head]
  while (curr) {
    // 生成新节点
    const node = new ListNode(curr.val)
    // 连接
    prev.next = node
    // 步进
    curr = curr.next
    // 更新前置节点
    prev = node
  }
  return dummy.next
}

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

深拷贝带随机指针的链表 ​

138. 复制带随机指针的链表

使用hashTable或hashMap ​

解题思路

初始化指向头节点的curr指针和映射表map:

  • 遍历链表：
    • 复制节点，并建立原节点 -> 新节点的映射表；
  • 再次遍历链表，构建新链表的引用指向：
    • 构建新表的.next指针引用指向；
    • 构建新表的.random指针引用指向。

返回新链表的表头map.get(head)。

JavaScript
const copyRandomList = head => {
  if (!head) return head
  let [curr, map] = [head, new Map()]
  // 复制各节点，建立 “原节点 -> 新节点” 的 Map 映射
  while (curr) {
    map.set(curr, new Node(curr.val))
    curr = curr.next
  }
  curr = head
  // 构建新节点的 next 和 random 指向
  while (curr) {
    map.get(curr).next = map.get(curr.next) || null
    map.get(curr).random = map.get(curr.random)
    curr = curr.next
  }
  // 返回新链表的头节点
  return map.get(head)
}

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

拼接与拆分 ​

解题思路

考虑构建原节点1 -> 新节点1 -> 原节点2 -> 新节点2 -> ……的拼接链表， 如此便可在访问原节点的random指向节点的同时找到新对应新节点的random指向节点：

  • 复制各节点，构建拼接链表；
  • 构建新链表各节点的random指向：
    • 当访问原节点curr的随机指向节点curr.random时，对应新节点curr.next的随机指向节点为curr.random.next。
    图示

    深拷贝

  • 拆分原链表与新链表：
    • 设置prev、curr分别指向原链表与新链表的头节点，遍历执行prev.next = prev.next.next和curr.next = curr.next.next将两链表拆分开。

返回新链表的表头。

JavaScript
const copyRandomList = head => {
  if (!head) return head
  let curr = head
  while (curr) {  // 深拷贝并拼接链表
    curr.next = new Node(curr.val, curr.next)
    curr = curr.next.next
  }
  curr = head
  while (curr) {  // 给 .random 指针赋值
    // 此时链表为复制拼接后的链表，节点加倍了，
    // 所以 curr.random.next 才指向 curr.next 的 random 节点
    curr.random && (curr.next.random = curr.random.next)
    curr = curr.next.next
  }
  let [newNode, newHead] = [head.next, head.next]
  curr = head
  while (curr.next && newNode.next) {  // 拆分
    curr.next = curr.next.next
    newNode.next = newNode.next.next
    curr = curr.next
    newNode = newNode.next
  }
  // 切断
  curr.next = null
  return newHead
}

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