题解 | #复杂链表的复制#

克隆结点->克隆随机指针->奇偶链表分离

以下cur均用在原来的结点上，而克隆得到的结点都用的是temp或clone_cur或clone_head。

// 克隆, 让 A->B 变成 A->A'->B->B'
void CloneNode(RandomListNode* head) {
  if (head == nullptr) return;
  RandomListNode* cur = head;
  while (cur) {
    auto temp = new RandomListNode(cur->label);
    temp->next = cur->next;
    cur->next = temp;
    cur = temp->next;
  }
}

// 克隆, 比如 A->random = B, 那么 A'->random = B', 其中 B' == B->next
void CloneRandomPtr(RandomListNode* head) {
  if (head == nullptr) return;
  RandomListNode* cur = head;
  while (cur) {
    RandomListNode* temp = cur->next;
    if (cur->random) {  // 一定要判空!!!
      temp->random = cur->random->next;
    }
    cur = temp->next;
  }
}

// 奇偶链表分离
RandomListNode* Reconnect(RandomListNode* head) {
  if (head == nullptr) return nullptr;
  RandomListNode* cur = head;
  RandomListNode* clone_head = nullptr;
  RandomListNode* clone_cur = nullptr;
  if (cur) { // 处理只有两个结点的情况
    clone_head = cur->next;
    clone_cur = clone_head;
    cur->next = clone_cur->next;
    cur = cur->next;
  }
  while (cur) {
    clone_cur->next = cur->next;
    clone_cur = clone_cur->next;
    cur->next = clone_cur->next;
    cur = cur->next;
  }
  return clone_head;
}
RandomListNode* Clone(RandomListNode* pHead) {
  if (pHead == nullptr) return nullptr;
  CloneNode(pHead);           // 1. 克隆结点
  CloneRandomPtr(pHead);      // 2. 克隆随机指针
  return Reconnect(pHead);    // 3. 奇偶链表分离
}