题目描述

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.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

样例

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

算法1

迭代+哈希表 $O(n)$

因为使用next节点可以保证遍历到所有的节点，所以我们使用next节点进行遍历。在遍历的时候每次把next节点放入哈希表中，这样方便检查在检查是否生成random节点中防止重复生成。

时间复杂度

因为每次遍历整个链表需要$O(n)$，空间上不算生成的节点需要$O(2 \times n)$来建立哈希表。

C++ 代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    unordered_map<Node*, Node*> m;
    Node* copyRandomList(Node* head) {
        if (!head) return NULL;
        Node* newHead = new Node(head -> val);
        Node* cpy = newHead;
        m[head] = newHead; // don't forget to put newHead into the map!!!
        while (head) {
            if (head -> next) {
                if (!m.count(head -> next))
                    m[head -> next] = new Node(head -> next -> val);
                cpy -> next = m[head -> next];
            }

            if (head -> random) {
                if (!m.count(head -> random))
                    m[head -> random] = new Node(head -> random -> val);
                cpy -> random = m[head -> random];
            }
            head = head -> next;
            cpy = cpy -> next;
        }
        return newHead;
    }
};

算法2

递归+哈希表 $O(n)$

同样的思路也可以应用于图的遍历。对于Node* copyRandomList(Node* head) {这个函数的物理意义是：copy一个当前head节点和他其他所有next和random节点，并且返回这个已经copy好的节点。这样base case就很清晰：如果head是空，那么返回NULL，如果head已经存在于哈希表中，那么我们直接返回deep copy好的这个节点。

时间复杂度

由于每次recursion call最终会被call n次（不是random的指针的数量，因为如果多次访问已经存在的节点就可以直接剪枝使用之前已经生成的节点来返回，不会再进行递归调用），所以时间是$O(n)$。空间上除了哈希表的大小还需要计算call stack的大小，即$O(n + 2 n)$

C++ 代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    unordered_map<Node*, Node*> m;
    Node* copyRandomList(Node* head) {
        if (!head) return NULL;
        if (m.count(head)) return m[head];
        Node* newHead = new Node(head -> val);
        m[head] = newHead;
        newHead -> next = copyRandomList(head -> next);
        newHead -> random = copyRandomList(head -> random);
        return newHead;
    }
};

算法3

迭代+无哈希表 $O(n)$

1. 首先在每一个curr, curr -> next中添加一个新的节点即：curr, newNext, curr -> next。
2. 第二步是添加所有的random指针，注意此时所有的节点已经存在，所以只需要添加所有的random指针即可。
3. 最后一步是断开所有的next节点，因为此时我们已经遍历并且安装了所有的random指针。

时间复杂度

因为每次遍历整个链表需要$O(n)$，空间上不再需要使用哈希表所以是$O(1)$.

C++ 代码

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
 public:
  RandomListNode *copyRandomList(RandomListNode *head) {
    if (!head) return NULL;
    RandomListNode *newHead, *l1, *l2;
    for (l1 = head; l1 != NULL; l1 = l1->next->next) {
      l2 = new RandomListNode(l1->label);
      l2->next = l1->next;
      l1->next = l2;
    }

    for (l1 = head; l1 != NULL; l1 = l1->next->next) {
      if (l1->random) l1->next->random = l1->random->next;
    }

    newHead = head->next;
    for (l1 = head; l1 != NULL; l1 = l1->next) {
      l2 = l1->next;
      l1->next = l2->next;
      if (l2->next) l2->next = l2->next->next;
    }

    return newHead;
  }
};

最后欢迎访问我的个人算法总结网站：http://advpetc.github.io/tech_notes