目录

1.题目链接

2.1解法①(暴力)

2.1.1解法思路：

2.1.2代码实现：

2.2解法②(进阶)

2.1.1解法思路：

2.2.2代码实现：

1.题目链接

138. 复制带随机指针的链表 - 力扣（LeetCode）

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 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;}//给定randomcur = 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;
}

以上就是本博客的所有内容了！