daily pastebin goal
35%
SHARE
TWEET

Untitled

a guest Mar 22nd, 2019 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     Node* next;
  7.     Node* random;
  8.  
  9.     Node() {}
  10.  
  11.     Node(int _val, Node* _next, Node* _random) {
  12.         val = _val;
  13.         next = _next;
  14.         random = _random;
  15.     }
  16. };
  17. */
  18. class Solution {
  19. public:
  20.   Node* copyRandomList(Node* head) {
  21.     if (!head) return head;
  22.     auto* new_list_head = head; // A
  23.     auto* new_list_curr_iter = new_list_head;
  24.    
  25.     // create A->A1->B->B1->C->C1->nullptr new nodes
  26.     while (new_list_curr_iter) {
  27.       auto* tmp = new_list_curr_iter->next;
  28.       new_list_curr_iter->next = new Node(new_list_curr_iter->val, tmp, new_list_curr_iter->random); // A1
  29.       new_list_curr_iter = tmp;
  30.     }
  31.      
  32.     // update random pointers
  33.     new_list_curr_iter = new_list_head;
  34.     while (new_list_curr_iter) {
  35.       new_list_curr_iter = new_list_curr_iter->next; // A1, B1 ...
  36.       if (new_list_curr_iter->random)
  37.         new_list_curr_iter->random = new_list_curr_iter->random->next;
  38.       new_list_curr_iter = new_list_curr_iter->next;
  39.     }
  40.      
  41.     // remove refs on original nodes
  42.     auto* old_list_curr_iter = head; // A
  43.     new_list_curr_iter = new_list_head->next; // A1
  44.     new_list_head = new_list_head->next;
  45.     while (new_list_curr_iter->next) {
  46.       old_list_curr_iter->next = old_list_curr_iter->next->next;
  47.       old_list_curr_iter = old_list_curr_iter->next;
  48.       new_list_curr_iter->next = new_list_curr_iter->next->next;
  49.       new_list_curr_iter = new_list_curr_iter->next;
  50.     }
  51.      
  52.     old_list_curr_iter->next = nullptr;
  53.     return new_list_head;
  54.   }
  55. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top