题目

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路

用map来保存<N，N>，其中一个是p.next指正，一个是p.random指针

代码

function RandomListNode(x) {
  this.label = x;
  this.next = null;
  this.random = null;
}
function Clone(pHead) {
  // write code here
  if (pHead === null) {
    return null;
  }
  const map = new Map();
  let p, p2;
  p = pHead;
  p2 = new RandomListNode(pHead.label);
  const pHead2 = p2;
  map.set(p, p2);
  while (p) {
    if (p.next) p2.next = new RandomListNode(p.next.label);
    else p2.next = null;
    p = p.next;
    p2 = p2.next;
    map.set(p, p2);
  }
  p = pHead;
  p2 = pHead2;
  while (p !== null) {
    p2.random = map.get(p.random);
    p = p.next;
    p2 = p2.next;
  }
  return pHead2;
}