LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 在每个节点之后插入一个与该节点相同的新节点，以便后续拷贝随机节点，最后把新建节点拆分出来即可

class Solution {
 public:
  Node* copyRandomList(Node* head) {
    if (!head) {
      return nullptr;
    }
    Node* cur = head;
    // 在每个节点后创建一个新节点
    while (cur) {
      Node* t = new Node(cur->val);
      t->next = cur->next;
      cur->next = t;
      cur = t->next;
    }
    // 拷贝随机节点
    cur = head;
    while (cur) {
      if (cur->random) {
        cur->next->random = cur->random->next;
      }
      cur = cur->next->next;
    }
    // 拆分链表
    cur = head;
    Node* dummy = new Node(-1);
    Node* t = dummy;
    while (cur) {
      t->next = cur->next;
      t = t->next;
      cur->next = cur->next->next;
      cur = cur->next;
    }
    return dummy->next;
  }
};

• 用哈希表保存节点

class Solution {
 public:
  Node* copyRandomList(Node* head) {
    if (!head) {
      return nullptr;
    }
    unordered_map<Node*, Node*> m;
    Node* cur = head;
    while (cur) {
      Node* t = new Node(cur->val);
      m[cur] = t;
      cur = cur->next;
    }
    cur = head;
    while (cur) {
      m[cur]->next = m[cur->next];
      m[cur]->random = m[cur->random];
      cur = cur->next;
    }
    return m[head];
  }
};