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

  • -1
    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 {
      RandomListNode copyRandomList(RandomListNode head) {
      int len = 0;
      for (RandomListNode iter=head; iter; iter=iter->next) len++;
      if (len==0)
      return NULL;
      result = reinterpret_cast<RandomListNode
      >(new char[len
      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;
      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.