Question

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example 1:

Input:

{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:

  • Node 1's value is 1, both of its next and random pointer points to Node 2.
  • Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

  1. You must return the copy of the given head as a reference to the cloned list.

Difficulty:Medium

Category:HashTable, Linked List

Analyze

这道题目看上去是比较麻烦的,因为你不能够同时完成所有内容的Deep copy, 因为每个节点的random是不知道的,所以是不能够在第一次拷贝的时候就完全完成拷贝。可以分成下面几个步骤完成。

  • 在当前节点中,拷贝一个节点包含了Next节点以及int label的数值,然后将这个节点添加到当前现在的list里面去,最后在将其分出来。
  • 完成 rondom 节点内容的拷贝工作
  • 分解两个List

Solution

Solution 1: Iterative

Use the next pointer of each node to store its copy.

Time complexity: O(1), Space complexity: O(1)

class Solution {
 public:
  Node* copyRandomList(Node* head) {
    Node dummy(-1, nullptr, nullptr);
    Node* new_cur = &dummy;

    // Copy the Next node and val
    // Add it after the original node
    for (Node* cur = head; cur != nullptr;) {
      Node* node = new Node(cur->val, nullptr, nullptr);
      node->next = cur->next;
      cur->next = node;
      cur = node->next;
    }

    // Copy the random node
    for (Node* cur = head; cur != nullptr;) {
      // Copy the random node
      if (cur->random != nullptr) cur->next->random = cur->random->next;
      cur = cur->next->next;
    }

    for (Node* cur = head; cur != nullptr;) {
      new_cur->next = cur->next;
      new_cur = new_cur->next;
      cur->next = cur->next->next;
      cur = cur->next;
    }

    return dummy.next;
  }
};

另外一种写法:

class Solution {
 public:
  Node* copyRandomList(Node* head) {
    if (!head) {
      return NULL;
    }
    copies[head] = new Node(head->val, NULL, NULL);
    Node* node = head;
    while (node) {
      Node *next = node->next, *random = node->random;
      if (next && copies.find(next) == copies.end()) {
        copies[next] = new Node(next->val, NULL, NULL);
      }
      if (random && copies.find(random) == copies.end()) {
        copies[random] = new Node(random->val, NULL, NULL);
      }
      copies[node]->next = next ? copies[next] : NULL;
      copies[node]->random = random ? copies[random] : NULL;
      node = next;
    }
    return copies[head];
  }

 private:
  unordered_map<Node*, Node*> copies;
};

Solution 2: Recursive

class Solution {
 public:
  Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    if (copies.find(head) == copies.end()) {
      copies[head] = new Node(head->val, NULL, NULL);
      copies[head]->next = copyRandomList(head->next);
      copies[head]->random = copyRandomList(head->random);
    }
    return copies[head];
  }

 private:
  unordered_map<Node*, Node*> copies;
};
By guozetang            Updated: 2020-09-19 13:02:30

results matching ""

    No results matching ""