A new method of O(n) time and O(1) space


  • -1
    W
    1. allocate all the memory for the copy of list, the list is actually
      an array where the next point of result[i] is &result[i+1]

    2. Initialize the copy of list. The next pointer of copy point to its
      original node, and the next of original pointing to the copy
      therefore we have two way map

    3. Using the two way map to find the correct random of copy

    4. restore the modified next of original list, and the copy list

      class Solution {
      public:
      RandomListNode copyRandomList(RandomListNode head) {
      int len = 0;
      for (RandomListNode iter=head; iter; iter=iter->next) len++;
      if (len==0)
      return NULL;
      RandomListNode
      result = reinterpret_cast<RandomListNode
      >(new char[len
      sizeof(RandomListNode)]);
      RandomListNode *iter=head;
      for (int i=0; iter; i++) {
      result[i].label = iter->label;
      result[i].next = iter;
      RandomListNode *next = iter->next;
      iter->next = result+i;
      iter = next;
      }
      for (int i=0; i<len; i++) {
      if (result[i].next->random)
      result[i].random = result[i].next->random->next;
      else
      result[i].random = NULL;
      }
      for (int i=0; i<len-1; i++) {
      result[i].next->next = result[i+1].next;
      result[i].next = result+i+1;
      }
      result[len-1].next->next = NULL;
      result[len-1].next = NULL;
      return result;
      }
      };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.