【初阶数据结构题目】14.随机链表的复制
随机链表的复制
点击链接做题
思路：
浅拷贝：拷贝值
深拷贝：拷贝空间
- 在原链表的基础上继续复制链表
- 置
random指针- 复制链表和原链表断开
代码：
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/
typedef struct Node Node;
Node* buyNode(int x){Node* newnode = (Node*)malloc(sizeof(Node));newnode->val = x;newnode->next = newnode->random = NULL;return newnode;
}
void AddNode(Node* phead){Node* pcur = phead;while(pcur){Node* Next = pcur->next;//创建新结点，尾插到pcurNode* newnode = buyNode(pcur->val);//newnode是复制结点pcur->next = newnode;newnode->next = Next;pcur = Next;}
}struct Node* copyRandomList(struct Node* head) {if(head == NULL){return NULL;}//1.原链表上复制结点AddNode(head);//2.置randomNode* pcur = head;while(pcur){Node* copy = pcur->next;if(pcur->random != NULL){copy->random = pcur->random->next;}pcur = copy->next;}//3.断开链表//在copy的链表里面设置两个指针：newHead,newTail位于拷贝链表的头//pcur往后挪两个到newHead->next，newTail挪到pcur->nextpcur = head;//让pcur先回到头节点Node* newHead, *newTail;newHead = newTail = pcur->next;while(pcur->next->next){//如果pcur->next->next为空就说明结束了pcur = pcur->next->next;newTail->next = pcur->next;//让newTail->next指向copy链表的后一个元素newTail = newTail->next;//把newTail移到copy链表的后一个元素的位置}return newHead;//返回新链表newHead到newTail
}