Copy List with Random Pointer
Desicription
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
|
class Solution { public: RandomListNode* copyRandomList(RandomListNode* head) { if(head == NULL) return NULL; for(RandomListNode* l1 = head; l1 != NULL; l1 = l1->next) { RandomListNode* l2 = new RandomListNode(l1->label); l2->next = l1->random; l1->random = l2; } for(RandomListNode* l1 = head; l1 != NULL; l1 = l1->next) { RandomListNode* l2 = l1->random; l2->random = l2->next?l2->next->random:NULL; } RandomListNode* newHead = head->random; for(RandomListNode* l1 = head; l1 != NULL; l1 = l1->next) { RandomListNode* l2 = l1->random; l1->random = l2->next; l2->next = l1->next?l1->next->random:NULL; } return newHead; } };
|