C++刷剑指offer(面试题35. 复杂链表的复制)【链表】
本帖最后由 糖逗 于 2020-5-8 17:45 编辑题目描述：
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
输入：head = [,,,,]
输出：[,,,,]
示例 2：
输入：head = [,]
输出：[,]
示例 3：
输入：head = [,,]
输出：[,,]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
提示：
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/*
// 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 head;
Node* temp1 = head;
while(temp1){
Node* new_node = new Node(temp1 -> val);
Node* store = temp1 -> next;
temp1 -> next = new_node;
new_node -> next = store;
temp1 = store;
}
temp1 = head;
while(temp1){
Node* temp2 = temp1 -> next;
if(temp1 -> random){
temp2-> random = temp1 ->random -> next;
}
else{
temp2 -> random = NULL;
}
temp1 = temp2 -> next;
}
Node* old = head;
Node* res = head -> next;
Node* new_head = head -> next;
while(new_head->next && new_head){
Node* old1 = new_head -> next;
Node* new1 = old1 -> next;
old -> next = old1;
new_head -> next = new1;
old = old1;
new_head = new1;
}
if(old)
old->next=nullptr;
return res;
}
};
注意事项：
1.大致思路如图1
2.if(old)
old->next=nullptr;
这行代码保证以前的链的最后一个元素指向null指针
页:
[1]