力扣 138. 随机链表的复制

题目描述：

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

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

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

思路：

题目要求我们拷贝一个带next指针与random随机访问指针的链表。

如果拷贝一个只带next指针的链表话呢，很简单，根据next依次遍历目标链表，再依次拷贝每个节点的信息就可以了.

一步一步来，我们可以先根据next“这条线” 先拷贝一个新的链表出来。

为什么不是优先根据random指针来拷贝呢？

这是因为random指针指向的是随机节点，可能有环存在，而且，random指向的节点有可能是很后面才出现的节点，而next在题目给出节点目标信息时关系就确定是线性不成环的，所以我们优先考虑拷贝next联系。

 如何拷贝各个节点的random联系呢？--本题重点

首先，我们假设每一个random关系是一条有向边，在旧链表中存在random关系(A)-->(B),

那么对应的，我们想让复制出来的新链表也有这么一条边，且为(a)-->(b)

那么如果我们能通过（A）找到（a）,通过（B）找到（b）,在遍历旧链表的random关系链中，我们就能顺便建立复制体的关系。（其中节点a是A的复制节点，b是B的复制节点）

也就是说，只要我们能通过某种联系找到自己的复制体，那么我们就能复制random联系。

于是题目的关键转移到了如何将这种联系该存下来且能快速找到呢？

根据哈希思想给出以下解法：

解法一：

如果是c++的话，可以用STL库中的map容器来存下旧链节点在新链的复制体节点。

也就是达到hash[A]=a,hash[B]=b.

unordered_map Hash({{NULL, NULL},{head, newhead}});

我这里照顾只学了c语言的朋友，主要讲方法二，不用map容器。

解法二：

改变旧链表的next,使其在被复制完后指向对应的复制体节点。

这里说的复制完是指复制val信息，以及next联系.

在复制next信息时，假设遍历到了A节点，首先用一个临时遍历temp存放A->next。

当我们创造出来了复制体a节点，我们让A->next=a,然后，a->random=A->random.

在将temp里的节点取出来继续遍历。

为什么要 a->random=A->random？

这是因为由于我们已经破坏了目标链表的next关系，我们之后再想复制random关系就不能再遍历旧链表了，仅依靠random关系可能出现环等问题，所以要想复制random关系，我们就要遍历新链表，也就是刚被复制出来的不完全体。

遍历到当前节点a,我们想要找a 的random应该指向哪里，我们可以先找到A的random指向的B，再通过B->next找到b，又因为A的random终点已经被赋给了a->random，所以就有了最重要的一步：

a->random=a->random->next.

这里a->random->next就是指向b节点。

重复以上步骤，就可以将所有random关系复制下来。

解法三：

思路和方法二差不多，只不过是将a->next=A -->next  然后A->next=a.这样一来，在破坏旧链的next关系后我们通过依旧可以通过A->next->next找到原来A的下一个节点。

这样我们再将a->random=A->random->next（先在目标链中找到B,再通过B->next找到b）.

这个方法只不过是恢复了旧链的可遍历性而已，和方法二差不多。

代码：

#define _CRT_SECURE_NO_WARNINGS 1
 
struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)return NULL;
    struct Node* phead = head;
    struct Node* newhead = (struct Node*)malloc(sizeof(struct Node));//新链的头指针
    struct Node* np = newhead;
    struct Node* star = newhead;
    while (phead) {
        struct Node* t = phead->next;//临时变量，存放phead的下一个节点，防止丢失
        newhead->val = phead->val;
        newhead->random = phead->random;//为了方便后续建立random联系
        phead->next = newhead;//哈希的思想，建立新、旧两个节点的联系
        if (t == NULL) {//如果下一个节点是NULL,就不用开辟空间了
            newhead->next = NULL;
        }
        else {//否则就创造一个节点空间，建立next关系
            newhead->next = (struct Node*)malloc(sizeof(struct Node));
            newhead = newhead->next;
        }
        phead = t;
    }
 
    while (np != NULL) {
        if (np->random != NULL) {
            np->random = np->random->next;//通过旧链找到新链应该指向的节点
        }
        np = np->next;
    }
    return star;
 
}

总结：

这个题总的来说不难，如果想用c写出来的话就要求对链表比较熟悉，还是比较考验基本功滴！