1.题目链接
2.1解法①(暴力)
2.1.1解法思路：
时间复杂度：O(N^2) 空间复杂度O(N);
①先遍历原链表，复制出一个一模一样的单链表，先不管random的问题；
②然后再遍历新生成的链表，同时进行random指针的拷贝：
这个实现是对于新生成的每一个节点，然后找到原链表的对应的节点，然后遍历原链表找出原链表对应的random指针指向的节点，计算random指向的节点和原链表中对应的节点的相对位置i；
然后在新生成的单链表中找到相同相对位置的节点，然后再将新生成的单链表中的该节点的random指向这个相对位置对应的节点。
2.1.2代码实现：
struct Node* BuyNode(int x) { struct Node* New = (struct Node*)malloc(sizeof(struct Node)); New->val = x; New->next = NULL; New->random = NULL; return New; } int CheckList(struct Node* head, struct Node*cur) { int x = 0; while(cur->random != head) { head = head->next; x++; } return x; } struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; struct Node* temp = BuyNode(-1); struct Node* pre = temp; //先复制单链表 while(cur) { temp->next = BuyNode(cur->val); temp = temp->next; cur = cur->next; } //复制随机指针 //1遍历原链表，遇到随即指针不为空的节点； //2然后再遍历链表找到随即指针指向的节点，计算位置； //3然后放入新的链表中 temp = pre->next;//初始化新链表箭头 cur = head;//初始化旧链表指针 while(cur) { if(cur->random != NULL) { int x = CheckList(head, cur); struct Node* shead = pre->next; for(int i = 0; i < x; i++) { shead = shead->next; } temp->random = shead; } cur = cur->next; temp = temp->next; } return pre->next; }
2.2解法②(进阶)
2.1.1解法思路：
①先进行如下的操作：
在每个节点后面插入一个新的节点然后每个节点的val和前一个节点相同；
②然后要做的就是处理新插入节点的random指针，进行第一步的操作就是为了方便第二步来处理random指针的：具体实现的方法就是给定一个指针cur来遍历原来就有的节点，然后遇到random指针不为空的节点，然后就将其next的random指向其的random的next即可；
（这个是最关键的）实现如下的效果；
③第三步也是最后一步，然后将那些在原链表上插入的新节点按顺序，尾插成一个新的链表；
2.2.2代码实现：
struct Node* BuyNode(int x) { struct Node* New = (struct Node*)malloc(sizeof(struct Node)); New->val = x; New->next = NULL; New->random = NULL; return New; } struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; //先复制单链表 while(cur) { struct Node* cnext = cur->next; struct Node* New = BuyNode(cur->val); cur->next = New; New->next = cnext; cur = cur->next->next; } //给定random cur = head; while(cur) { if(cur->random) { cur->next->random = cur->random->next; } cur = cur->next->next; } //生成新链表 cur = head; struct Node* Bhead = (struct Node*)malloc(sizeof(struct Node)); Bhead->next = NULL; struct Node* tail = Bhead; int x = 1; while(cur) { if(x % 2 == 0) { tail->next = cur; tail = tail->next; } x++; cur = cur->next; } return Bhead->next; }
以上就是本博客的所有内容了！
