https://oj.leetcode.com/problems/copy-list-with-random-pointer/
灵活的指针链表应用。
每个节点有两个指针next,random,对本链表做一个深拷贝。就是完全用新内存弄出一个一样的来。
a链表: a b c三个node
b链表: a1 b1 c1三个node
a->next = a1
a1->next = b
这样建立关系,之后再扫一遍,对a1的random赋值,之后再扫一遍,对a1->next赋值。
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; struct RandomListNode { int label; RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) {} }; class Solution { public: RandomListNode *copyRandomList(RandomListNode *head) { if(head == NULL) return NULL; for(RandomListNode *pointer = head;pointer!=nullptr;) { RandomListNode *link2node = new RandomListNode(pointer->label); link2node->next = pointer->next; pointer->next = link2node; pointer = pointer->next->next; } for(RandomListNode *pointer = head;pointer!=nullptr;) { if(pointer->random!=NULL) pointer->next->random = pointer->random->next; pointer = pointer->next->next; } RandomListNode *head2 = head->next; RandomListNode * pointer2 = nullptr; for(RandomListNode *pointer = head;pointer!=nullptr;pointer = pointer->next) { pointer2 = pointer->next->next; if(pointer2 != nullptr) { pointer->next->next = pointer->next->next->next; pointer->next = pointer2; } else { pointer->next->next = NULL; pointer->next = NULL; } } return head2; } }; int main() { RandomListNode *n1 = new RandomListNode(1); RandomListNode *n2 = new RandomListNode(2); RandomListNode *n3 = new RandomListNode(3); RandomListNode *n4 = new RandomListNode(4); n1->next = n2; n2->next = n3; n3->next = n4; n1->random = n2; n2->random = n1; n4->random = n4; class Solution mys; mys.copyRandomList(n1); }