leetcode138.复制带随机指针的链表

题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

思路

方法一：回溯

回溯算法的第一想法是将链表想象成一张图。链表中每个节点都有 2 个指针（图中的边）。因为随机指针给图结构添加了随机性，所以我们可能会访问相同的节点多次，这样就形成了环。此方法中，我们只需要遍历整个图并拷贝它。拷贝的意思是每当遇到一个新的未访问过的节点，你都需要创造一个新的节点。遍历按照深度优先进行。我们需要在回溯的过程中记录已经访问过的节点，否则因为随机指针的存在我们可能会产生死循环。

1、从 头 指针开始遍历整个图。Head是图中出发点。

2、当我们遍历到某个点时，如果我们已经有了当前节点的一个拷贝，我们不需要重复进行拷贝。

3、如果我们还没拷贝过当前节点，我们创造一个新的节点，并把该节点放到已访问字典中。

4、根据next和random分别做递归遍历。

代码：

 1 class Solution {
 2     unordered_map<Node*, Node*> map;
 3 public:
 4     //将链表视作一张图，通过next和random两条路径遍历该图
 5     Node* copyRandomList(Node* head) {
 6         if (!head) return head;
 7         //如果当前节点已经被访问，则直接返回
 8         if (set.count(head)) return map[head];
 9     
10         Node* node = new Node(head->val);
11         map[head] = node;
12 
13         node->next = copyRandomList(head->next);
14         node->random = copyRandomList(head->random);
15 
16         return node;
17     }
18 };

方法二：O(1)空间的迭代

与上面提到的维护一个旧节点和新节点对应的字典不同，我们通过扭曲原来的链表，并将每个拷贝节点都放在原来对应节点的旁边。这种旧节点和新节点交错的方法让我们可以在不需要额外空间的情况下解决这个问题。

1、遍历原来的链表并拷贝每一个节点，将拷贝的节点放在原来节点的旁边，创造出一个纠结点和新节点交错的链表。

2、迭代这个新旧节点交错的链表，并用旧节点的random指针去更新新节点的random指针。

3、现在random指针已经被赋值给了正确的节点，next指针也需要被正确赋值，以便将新的节点正确链接同时将旧节点重新正确连接。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL) return head;
        Node *p = head;
        //1.把每个旧节点生成一个新节点紧跟其后
        while (p) {
            Node *newNode = new Node(p->val);
            newNode->next = p->next;
            p->next = newNode;
            p = newNode->next;
        }
        //2.重头开始遍历，将每个新节点的random置好
        p = head;
        while (p && p->next) {
            if (p->random)
                p->next->random = p->random->next;
            p = p->next->next;
        }
        //3.重头开始将新旧节点拆成两条链
        p = head;
        Node *res = head->next;
        while (p->next) {
            Node *pNext = p->next;
            p->next = pNext->next;
            p = pNext;
        }
        return res;
    }
};