复杂链表的复制

题目： 

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。（题目来自剑指Offer）


示例：


解法：

let copyRandomList = (head) => {
  if (!head) return null;
  let map = new Map();
  let newHead = new Node(head.val),
    node = head,
    newNode = newHead;
  // 将node与newNode关联起来，方便后面复制随机节点
  map.set(node, newNode);
  // 循环复制单链表
  while (node.next) {
    newNode.next = new Node(node.next.val);
    node = node.next;
    newNode = newNode.next;
    map.set(node, newNode);
  }
  // 重置新节点和链头
  newNode = newHead;
  node = head;
  // 循环复制随机节点
  while (newNode) {
    newNode.random = map.get(node.random);
    newNode = newNode.next;
    node = node.next;
  }
  return newHead;
};

评论(0)

评论