复制带随机指针的链表

Node *copyRandomList(Node *head) {
  if (head == nullptr) return nullptr;

  // 复制链表，并把节点插在原节点后面
  Node *cur = head;
  while (cur != nullptr) {
    Node *nxt = cur->next;
    cur->next = new Node(cur->val, cur->next);
    cur = nxt;
  }

  // 复制随机指针
  cur = head;
  while (cur != nullptr) {
    cur->next->random = cur->random ? cur->random->next : nullptr;
    cur = cur->next->next;
  }
  // 分离链表
  Node dummy(0);
  Node *tail = &dummy;
  cur = head;
  while (cur != nullptr) {
    tail->next = cur->next;
    cur->next = tail->next->next;
    cur = cur->next;
    tail = tail->next;
  }
  return head;
}