题目描述

给你一个长度为 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的时候，原链表对应结点的random指针指向的结点的值记为goal，然后在新链表中找goal的值val所在的结点，然后所处理的复制链表的random指向这个找到的结点。这是错误的，因为我们要保证链表的对应关系没变，可能一个链表中有多个相同的val值，在原链表中如果对应结点的random指向的是第2个有这个val值的结点，而我们的处理手段会让复制链表的random指向第一个val的结点。

思路1

  我们首先复制出来一个链表：

  然后这样处理random指针，假设现在指向复制链表中需要处理random的结点的指针是copy，对应原链表中的对应结点的指针是cur，

• 如果cur->random==NULL，那么copy->random=NULL;
• 否则定义一个计数器count，cur从头开始走走到cur和原来cur的random相等的位置，每走一步计数器++，然后copy也从头开始走，走count步，然后原来copy的random就等于copy当前的位置。

struct Node* copyRandomList(struct Node* head) 
{struct Node* copyhead = NULL;struct Node* copytail = NULL;struct Node* cur = head;//利用尾插复制且处理新链表的nextwhile(cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next = NULL;if(copytail == NULL){copyhead = copytail = copy;}else{copy->next = copytail->next;copytail->next = copy;copytail = copy;}cur = cur->next;}//利用计数器处理random结点cur = head;struct Node* copy = copyhead;while(cur){struct Node* tmp = cur->random;if(tmp == NULL){copy->random = NULL;cur = cur->next;copy = copy->next;}else{int count = 0;struct Node* tmp1 = cur;cur = head;while(cur != tmp){count++;cur = cur->next;}cur = tmp1;struct Node* tmp2 = copy;copy = copyhead;while(count--){copy = copy->next;}tmp2->random = copy;copy = tmp2;cur = cur->next;copy = copy->next;}}return copyhead;	
}

缺点：时间复杂度太高，最坏情况下确定random每次都要走N步，外面再套一个循环，时间复杂度是O(n^2)。

思路2：

step1：首先我们在原链表的原结点后面插入一个复制结点，如图

//1.拷贝结点，然后把拷贝结点放到新结点的后面struct Node* cur = head;while(cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next = cur->next;cur->next = copy;cur = copy->next;}

step2：处理random，对于每个拷贝结点，定义指向这个拷贝结点的指针是copy=cur->next，定义其原结点的指针是cur，如果cur->random==NULL,则copy->random=NULL;否则根据我们现在的链表图：
$$copy->random=cur->random->next$$

然后cur=copy->next,一直走到cur==NULL，最终情况如图：

//2.处理拷贝结点的randomcur = head;while(cur){struct Node* copy = cur->next;if(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}cur = copy->next;}

step3:把新链表解下来，连起来，同时把原链表恢复。

  操作具体为定义一个copyHead和copyTail用来尾插，定义一个next=cur->next->next用来恢复原链表链接。

最终完成循环后

//3.把新链表解下来并且恢复原链表struct Node* copyHead = NULL;struct Node* copyTail = NULL;cur = head;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;if(copyTail == NULL){copyHead = copyTail = copy;copy->next = NULL;}else{copy->next = copyTail->next;copyTail->next = copy;copyTail = copy;}cur->next = next;cur = next;}

汇总：

struct Node* copyRandomList(struct Node* head) 
{//1.拷贝结点，然后把拷贝结点放到新结点的后面struct Node* cur = head;while(cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next = cur->next;cur->next = copy;cur = copy->next;}//2.处理拷贝结点的randomcur = head;while(cur){struct Node* copy = cur->next;if(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}cur = copy->next;}//3.把新链表解下来并且恢复原链表struct Node* copyHead = NULL;struct Node* copyTail = NULL;cur = head;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;if(copyTail == NULL){copyHead = copyTail = copy;copy->next = NULL;}else{copy->next = copyTail->next;copyTail->next = copy;copyTail = copy;}cur->next = next;cur = next;}return copyHead;	
}

  思路2涉及的操作有遍历原链表插入拷贝结点O(N)、处理random O(N)、恢复原链表并且把拷贝结点尾插O(N)，时间复杂度是O(N)。