题目

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

方法

办法：利用链表原链表结构特性
时间复杂度：n

思路

简单的办法，就是先复制一遍链表，再对原链表每个节点的random查找在原链表的下标，在新链表中做赋值。这个办法的复杂度是n2
另一个办法，我们可以利用链表的特性。先在原链表中的每个节点后插入一个新节点，作为节点的复制。然后新节点的radom不需要再寻找下标，因为原节点的radom如果不为null，那再上一步一定被复制了一个节点放在radom的后方，那么这个新的radom节点就是新节点的radom了

具体办法：
分为三步

• 在每个节点后插入一个值相等的节点
• 复制radom指针，复制节点的radom就是原节点radom的next
• 切断旧链表，将复制的链表连接起来

代码

function Clone(pHead) {
  // write code here
  // 1. 在每个节点后插入一个值相等的节点
  if (!pHead) return null
  let p = pHead
  while (p) {
    let node = new RandomListNode()
    node.label = p.label
    node.next = p.next
    p.next = node
    p = node.next
  }
  // 2. 复制radom指针，复制节点的radom就是原节点radom的next
  p = pHead
  while (p) {
    let copy = p.next
    copy.random = p.random ? p.random.next : null
    p = copy.next
  }
  // 3. 切断旧链表，将复制的链表连接起来
  let newHead = pHead.next
  p = newHead
  while (p.next) {
    p.next = p.next.next
    p = p.next
  }
  return newHead
}