题目
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { }
解题思路
思路一
要复制一个链表是简单的，但这个是带有随机指针的链表，你不能确定单节点的随机指针指向哪个，这就需要动一下脑筋了。可以发现这本身是一个单链表，即链表是单向链接的，随机指针指向的节点也都是单链表内的一个节点，所以我们可以采取一个数组来记忆每个单向节点中的random是指向第几个节点（这样同时可以避免一个问题，用val值标记的话如第二个节点和第五个节点（val 均为1），就难以分辨val=11节点的random应指向哪里，而采用顺序表进行存储random指向可以解决此问题）
如何实现？
如找到第三个节点（val=11）的random指向，就要采用嵌套循环，一个循环遍历链表random指向，一个循环存储到数组中对应位置。如图示：
但这样会有一个问题，时间复杂度为O(N^2), 要优化到O(N),就不能有两个嵌套循环。
思路2
如果我们复制一遍原单向链表，将新单链表与原单链表进行链接，是不是就可以通过仅遍历一遍将原单链表的random指针指向复制到新单链表上呢？ 通过画图可以发现是可行的：
//拷贝节点链接在源节点后面 struct Node* cur = head; while(cur) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); struct Node* next = cur->next; copy->val = cur->val; //进行链接 cur ->next = copy; copy->next = next; cur = next; }
如何链接拷贝节点的random？
我们用cur指针对原链表进行遍历，可以发现（如val =13 的copy节点），当cur指向val= 13 节点时，cur ->random 指向节点的下一个就是val= 7 的copy节点，也就是说 copy ->random = cur->random->next;
对剩余节点同样是适用的，当cur == NULL 时遍历结束， 同时应主要判断cur ->random 是否指向NULL和cur是否重置为头结点head，以便进行新一次遍历
// 链接拷贝节点的random cur = head; // 对cur 重置 while(cur) { struct Node*copy = cur ->next; struct Node* next = copy ->next; //设置next 指针，便于观察 if (cur ->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } cur = next; }
最后一步就是将拷贝节点拆解下来，进行链接成拷贝链表，同时可以把原链表恢复链接关系（不恢复OJ也能过），如何实现？只需利用尾插法再用cur指针遍历一遍，所以我们需要设置copyHead 指针（用于返回头节点）和copyTail指针用于尾插进行遍历
//拆解拷贝节点，链接组成拷贝链表 cur = head; struct Node* copyHead = NULL, *copyTail = NULL; while(cur) { struct Node* copy = cur ->next; struct Node* next = copy->next; //链接原链表 cur->next = next; //尾插拷贝链表 if(copyTail == NULL) { copyHead = copyTail = copy; } else { copyTail-> next = copy; //此处为下一个copy节点，如val=7的节点 下一个是val=13 copyTail = copyTail ->next; } cur = next; } return copyHead; }
本题利用了链表尾插，删除等思想，对指针掌握能力要求较高
这是题解：
struct Node* copyRandomList(struct Node* head) { //拷贝节点链接在源节点后面 struct Node* cur = head; while(cur) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); struct Node* next = cur->next; copy->val = cur->val; cur ->next = copy; copy->next = next; cur = next; } // 链接拷贝节点的random cur = head; while(cur) { struct Node*copy = cur ->next; struct Node* next = copy ->next; if (cur ->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } cur = next; } //拆解拷贝节点，链接组成拷贝链表 cur = head; struct Node* copyHead = NULL, *copyTail = NULL; while(cur) { struct Node* copy = cur ->next; struct Node* next = copy->next; //链接原链表 cur->next = next; //尾插拷贝链表 if(copyTail == NULL) { copyHead = copyTail = copy; } else { copyTail-> next = copy; //此处为下一个copy节点，如val=7的节点 下一个是val=13 copyTail = copyTail ->next; } cur = next; } return copyHead; }
本节完，有不懂可以私聊作者
