138. 随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

class Solution {
public:
  Node* copyRandomList(Node* head) {
    if (!head)
      return {};

    // Prepare old list.
    vector<Node *> List;
    Node *N = head;
    while (N) {
      List.push_back(N);
      N = N->next;
    }

    // Copy to new list and initialize all `next`s to new values,
    // but keep `random`s as old values.
    vector<Node *> NewList;
    Node *NewPrev = nullptr;
    for (auto *N : List) {
      Node *New = new Node(N->val);
      New->random = N->random;

      if (NewPrev)
        NewPrev->next = New;
      NewPrev = New;

      NewList.push_back(New);
    }

    // Fill `random` by utilizing continuous address space
    for (auto *N : NewList) {
      for (int i = 0; i < List.size(); ++i) {
        if (!N->random)
          break;

        if (N->random == List[i])
          N->random = NewList[i];
      }
    }

    return NewList.front();
  }
};

有点搞，我这个属于大力出奇迹，直接用数组把哈希表的活干了，导致复杂度是 $\mathrm O\left(n^2\right)$，而且也没有利用到递归性质，真就是一个一个 copy。

递归解法还是比较容易理解的，尤其是把函数签名当中的 head 改成 Old 之后看起来更清晰，是一个非常明显的经由哈希表使得新旧两组结点形成联系的解法。注意递归函数始终接受的都是 Old 的节点，返回的都是 New 的节点。

class Solution {
  unordered_map<Node *, Node *> OldNewPairs;
public:
  Node* copyRandomList(Node* Old) {
    if (!Old)
      return {};

    // Check if old node has not been visited,
    // otherwise dead loops will be introduced.
    if (!OldNewPairs.count(Old)) {
      Node *New = new Node(Old->val);
      OldNewPairs[Old] = New;
      New->next = copyRandomList(Old->next);
      New->random = copyRandomList(Old->random);
    }

    return OldNewPairs[Old];
  }
};

但是 unordered_map 的 API 需要再熟悉熟悉。二刷注意一下节点拆分法，挺好玩的。

二刷

class Solution {
  unordered_map<Node*, Node *> OldNew_;
public:
  Node* copyRandomList(Node* head) {
    if (!head)
      return {};

    auto It = OldNew_.find(head);
    if (It != OldNew_.end())
      return It->second;

    Node *New = new Node(head->val);
    OldNew_[head] = New;
    New->next = copyRandomList(head->next);
    New->random = copyRandomList(head->random);
    return New;
  }
};

哈希表递归的思路还是非常明确的，新旧映射，感觉没什么好讲的。节点拆分也试着写了一下。

class Solution {
public:
  Node* copyRandomList(Node* head) {
    Node *OldHead = head;

    if (!head)
      return {};

    // Duplicate list.
    while (head) {
      Node *Next = head->next;
      head->next = new Node(head->val);
      head->next->next = Next;
      head = Next;
    }

    // Copy random.
    head = OldHead;
    while (head) {
      if (head->random)
        head->next->random = head->random->next;
      head = head->next->next;
    }

    // Split two lists.
    head = OldHead;
    Node *NewHead = head->next;
    while (head) {
      Node *New = head->next;
      head->next = New->next;
      if (!New->next)
        break;
      New->next = New->next->next;
      New = New->next;
      head = head->next;
    }
    
    return NewHead;
  }
};

但其实我这个写复杂了，其实完全可以用 for 代替这里所有的 while，就像官解这样，还省心。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* nodeNew = new Node(node->val);
            nodeNew->next = node->next;
            node->next = nodeNew;
        }
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* nodeNew = node->next;
            nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
        }
        Node* headNew = head->next;
        for (Node* node = head; node != nullptr; node = node->next) {
            Node* nodeNew = node->next;
            node->next = node->next->next;
            nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
        }
        return headNew;
    }
};

三刷

class Solution {
public:
  Node* copyRandomList(Node* head) {
    if (!head)
      return {};

    // 1. Create new nodes after each old node.
    Node *Next, *NewHead;
    for (Node *Curr = head; Curr; Curr = Next) {
      Next = Curr->next;
      Curr->next = new Node(Curr->val);
      Curr->next->next = Next;
    }

    // 2. Fill in their random values ONLY, and keep nexts as-is.
    for (Node *Curr = head; Curr; Curr = Next) {
      Node *New = Curr->next;
      Next = Curr->next->next;
      if (Curr->random)
        New->random = Curr->random->next;
      else
        New->random = nullptr;
    }

    // 3. Break and reconnect nexts.
    NewHead = head->next;
    for (Node *Curr = head; Curr; Curr = Next) {
      Node *New = Curr->next;
      Next = Curr->next->next;
      Curr->next = Next;
      if (Next)
        New->next = Next->next;
      else
        New->next = nullptr;
    }

    return NewHead;
  }
};

注意，我们的三步分别是

在每个旧节点之后创建新节点，并将其连续地连接在整条链上；
对于每个新节点，依据 New == Curr->next 的关系，找到它们对应的新随机节点——但在此过程中，保留链表的连续性；
根据 New == Curr->next 的关系（这也是为什么我们要在第二步中保留连续性）将新旧链表断线重连。

在这个过程中要时刻警惕 Next 的边界条件，因为我们的结构是

$$ 1\to1'\to2\to2'\to3\to3'\to\emptyset $$

而不是

$$ 1\to1'\to2\to2'\to3\to3'\to\emptyset\to\emptyset' $$

此外，还应注意 random 可能为空，避免解引用空节点。

三刷

class Solution {
public:
  Node* copyRandomList(Node* head) {
    Node PreNew(0), *Prev = &PreNew;
    // 1. Duplicate.
    for (Node *This = head; This; This = This->next->next) {
      Node *Next = This->next;
      This->next = new Node(This->val);
      This->next->next = Next;
    }
    // 2. Fill random.
    for (Node *This = head; This; This = This->next->next) {
      if (This->random)
        This->next->random = This->random->next;
      else
        This->next->random = nullptr;
    }
    // 3. Disconnect and reconnect.
    for (Node *This = head; This; This = This->next) {
      Node *New = This->next;
      // Mind that This->next is already changed inside the body! So we only
      // advance ONCE the loop ends every time.
      This->next = This->next->next;
      Prev->next = New;
      Prev = New;
    }
    return PreNew.next;
  }
};

哎我操，这循环这样写有坑啊，最后一个循环条件当中的步进是一次而不是前两个当中的两次，因为我们在断链重连的时候已经在循环体里改过一次This->next了。