Description

算法步骤

双Map + 两次链表遍历

假如没有random指针，深拷贝一条普通链表，只需要按顺序复制链表的val和next指针，因为每个节点和下一个节点是按顺序一一对应的。现在增加了random指针带来的麻烦就是，当前复制节点的random可能还没有被遍历到并复制下来。所以无法在顺序遍历的时候直接确定下来random节点。由于我们知道不管怎样，链表上各节点的random总是指向链表上的其他节点的。如果我们能够记住新节点到旧节点的关系，先通过当前节点找回自己的旧节点，再从旧节点找到对应的原链表上的random节点。因为原链表上的这个random节点本身也是链表上的节点，那么我们可以再次映射回到新链表上的对应节点，而这个对应的新节点就是新的random节点。 比如1->2->3-null(old)，假设1的random是3。那么我们可以先复制除了random之外的所有属性，1->2->3-null(new)。接着我们建立两个map，分别是newToOld和oldToNew：

• newToOld的作用是通过新链表上的新节点A2找到原链表上的老节点A1，进而能够通过老节点找到自己的老random节点C1。
• oldToNew的作用是通过原链表上的老random节点C1找到自己在新链表上的新random节点C2。 这样一来我们就知道新节点A2的random其实就是C2了。让A2的random指向C2即可。遍历新链表完成所有random指向。

function copyRandomList(head: _Node | null): _Node | null {
  const dummy = new _Node(-1);
  let tail = dummy;
  let l1 = head;
  let l2 = dummy;
  const newToOld = new WeakMap<_Node, _Node>();
  const oldToNew = new WeakMap<_Node, _Node>();

  // 复制原链表
  while (l1) {
    l2 = new _Node(l1.val);
    tail.next = l2;

    newToOld.set(l2, l1);
    oldToNew.set(l1, l2);

    tail = tail.next;
    l1 = l1.next;
  }

  // 完成random指向
  l2 = dummy.next!;
  while (l2) {
    const old = newToOld.get(l2)!;
    const newRandom = oldToNew.get(old.random!)!;

    l2.random = newRandom;
    l2 = l2.next!;
  }

  return dummy.next;
};
Copy