复杂链表的复制
思路
如果不考虑random指针的复制，仅仅复制单链表的结构还是简单的。只需要通过一个指针cur遍历原链表，再不断创建新节点尾插到newHead后即可。
但如果要考虑random指针的复制，那过程就复杂了。
有小伙伴会这样想：既然原链表和复制的链表的结构一致，那么对于原链表的任意一个节点，我们都可以先知道它们random指针的指向，这样就可以通过循环得到这是原链表的第几个节点，最后也就可以通过循环将复制链表的相同节点的random指针指向相同的位置了。但是对于每一个节点，每确定一个random指针时间复杂度就是O(N)，一共N个节点时间复杂度就是O(N^2)，显然效率不高。
接下来给大家讲解一个时间复杂度为O(N)，空间复杂度为O(1)的方法：
- 第一步：新建节点，复制链表的
val值、next值
这里我们不采用新建一个头newHead，然后将新建的节点尾插到newHead后的方法。
这里我们利用交织链表的方法：cur遍历原链表，每遍历一个节点就将复制的节点插入到这个节点之后。形象一点来说就是，如果原链表为A->B->C->NULL，那么这一步过后，链表就变成了A->A'->B->B'->C->C'->NULL
struct Node* cur = head; //先创建交织链表 while (cur) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->val = cur->val; temp->next = cur->next; cur->next = temp; cur = cur->next->next; }
- 第二步：完成
random指针的复制
实现了上面交织链表的操作，我们就可以直接得到复制链表的节点的random指着的指向了：
即为其原节点S的随机指针指向的节点T的后继节点T'。需要注意原节点的随机指针可能为空，我们需要特别判断这种情况。
通过下图也可以理解对应的关系：
//复制random指针 cur = head; while (cur) { struct Node* temp = cur->random; //找到随机指针的指向 if (temp == NULL) cur->next->random = NULL; else cur->next->random = temp->next; cur = cur->next->next; }
- 最后一步，将交织的链表拆成两串链表，返回复制链表的头
虽然我们也可以不对原链表进行还原，但安全起见，最好不要改变原有的链表结构
struct Node* retHead = head->next; //要返回的头节点 struct Node* cur1 = head; struct Node* cur2 = retHead; //取消交织，还原为两个链表 while (cur1 && cur2->next) { cur1->next = cur1->next->next; cur2->next = cur2->next->next; cur1 = cur1->next; cur2 = cur2->next; } cur1->next = NULL; cur2->next = NULL; //最后返回复制链表 return retHead;
实现代码
struct Node* copyRandomList(struct Node* head) { if (head == NULL) return NULL; struct Node* cur = head; //先创建交织链表 while (cur) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->val = cur->val; temp->next = cur->next; cur->next = temp; cur = cur->next->next; } //复制随机指针 cur = head; while (cur) { struct Node* temp = cur->random; //找到随机指针的指向 if (temp == NULL) cur->next->random = NULL; else cur->next->random = temp->next; cur = cur->next->next; } //取消交织 struct Node* retHead = head->next; //要返回的头节点 struct Node* cur1 = head; struct Node* cur2 = retHead; //取消交织，还原为两个链表 while (cur1 && cur2->next) { cur1->next = cur1->next->next; cur2->next = cur2->next->next; cur1 = cur1->next; cur2 = cur2->next; } cur1->next = NULL; cur2->next = NULL; //最后返回复制链表 return retHead; }
