本文共 1124 字，大约阅读时间需要 3 分钟。

题目

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

思路

拿到题的思路就是hash表+两次遍历，但看到书上有更能节省空间的办法后就直接写了书上的。

翻了个错误就是奇偶链表节点的处理上，还是不能拿个整数做%2操作来判断，需要指针处理，因为最后一个空节点不复制。

总的来说就是三个方法顺序操作一下。

代码

/*// Definition for a Node.class Node {public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}};*/class Solution {public:
Node* copyRandomList(Node* head) {
if(head == NULL){
return NULL;
}
copyList(head);
changeptr(head);
return GetNewList(head);
}
void copyList(Node* head){
Node* p = head;
while(p != NULL){
Node* pclone = new Node(p->val);
Node* p1 = p->next;
p->next = pclone;
pclone->next = p1;
p=pclone->next;
}
}
void changeptr(Node* head){
Node* p = head;
while(p != NULL){
Node* pnew = p->next;
if(p->random != NULL){
pnew->random = p->random->next;
}
p=pnew->next;
}
}
Node* GetNewList(Node* head){
Node* p = head;
Node* pnewhead = NULL;
Node* pnew = NULL;
pnewhead = p->next;
pnew = p->next;
p->next = pnewhead->next;
p = p->next;
while(p != NULL){
pnew->next = p->next;
pnew = p->next;
p->next = pnew->next;
p=p->next;
}
return pnewhead;
}};

转载地址：https://blog.csdn.net/hanmin822/article/details/105699205 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！