①复制一个小弟,②然后复制random指针,然③后拆分两个链表。返回新链表即可。
复制小弟+random指针
恢复。拆分链表
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
/*
①复制一个小弟(在自己身后)
②复制random指针
③把两个链表拆开 【---》省去一个哈希表】
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
for (auto p = head; p; p = p->next->next){//① 注:第一个next是小弟,第二个next才是后一个点。
auto q = new Node(p -> val);
q->next = p->next;
p->next = q; //复制完把p指向这个小弟,(结果:p前面 -》p -》小弟q -》p后面
}
// ②
for (auto p = head; p; p = p->next->next)
if (p->random) //要判断一下有random再复制,否则空指针next会访问非法内存
p->next->random = p->random->next;
// ③
auto dummy = new Node(-1), cur = dummy; //记录新链表的尾节点 //新链表:dummy
for (auto p = head; p; p = p->next){
auto q = p->next;//小弟q 就是p.next
cur = cur->next = q; //小弟插到尾节点
p->next = q->next; //把p恢复原状。(原来的next)
}
return dummy->next; //返回新链表的next
}
};
请问这题是在哪个视频中讲的啊
leetcode究极班 138
好的,谢谢