nikunjsoni

138

Mar 20th, 2021
75
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(int _val) {
  10.         val = _val;
  11.         next = NULL;
  12.         random = NULL;
  13.     }
  14. };
  15. */
  16.  
  17. class Solution {
  18. public:
  19.     Node* copyRandomList(Node* head) {
  20.         if(!head) return NULL;
  21.         Node *curr = head;
  22.        
  23.         // Generate copy node and link it to list.
  24.         while(curr){
  25.             Node *dummy = new Node(curr->val);
  26.             dummy->next = curr->next;
  27.             curr->next = dummy;
  28.             curr = dummy->next;
  29.         }
  30.        
  31.         // Set random ptr of copy node.
  32.         curr = head;
  33.         while(curr){
  34.             curr->next->random = (curr->random) ? curr->random->next : NULL;
  35.             curr = curr->next->next;
  36.         }
  37.        
  38.         // Separate the list and return.
  39.         Node *newHead = head->next;
  40.         curr = head;
  41.         while(curr){
  42.             Node* tmp = curr->next->next;
  43.             curr->next->next = (tmp) ? tmp->next: NULL;
  44.             curr->next = tmp;
  45.             curr = tmp;
  46.         }
  47.         return newHead;
  48.     }
  49. };
RAW Paste Data