Why new list value sync the change in old list?


  • 1
    M

    My method is:

    1. create a new link list without random pointer (put NULL in random pointer);
      each time after added a new list node, store pointer that pointed to this new node to a pointer array, and change the 'label' value of old list node to pointer array index (the order of the node).

    2. scan from new list head to tail, find the index value from old list node 'label' value, put the pointer stored in this index as the random pointer for current new node

    The problem is new list 'label' value changes when put index to old list. Checked many times, still don't know why.

    Codes:

    /**
     * Definition for singly-linked list with a random pointer.
     * struct RandomListNode {
     *     int label;
     *     RandomListNode *next, *random;
     *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
     * };
     */
    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            // Note: The Solution object is instantiated only once and is reused by each test case.
            RandomListNode *res = new RandomListNode(0);
            RandomListNode *cur = head;
            RandomListNode *pre = res;
            
            int maxsize = 10000, n = 0;
            RandomListNode *add[maxsize];
            //RandomListNode *loc = new RandomListNode(0);
            
            while (cur!=NULL) {
                RandomListNode *node = new RandomListNode(cur->label);
                pre->next = node;
    
                add[n] = node;
                cur->label = n;
                n ++;
                
                pre = pre->next;
                cur = cur->next;
            }
            
            cur = head;
            pre = res->next;
            while (cur!=NULL) {
                if (cur->random!=NULL) pre->random = add[cur->random->label]; else pre->random = NULL;
                cur = cur->next;
                pre = pre->next;
            }
            
            return res->next;
        }
    };

  • 0

    Could you please format your code nicely? Select your code, and click on the {} button to format it.


  • 0
    M

    is it better now?


  • 0
    S

    Thanks, it looks much better!


  • 0
    J

    you should not use RandomListNode *res = new RandomListNode(0); you should create this in while (cur!=NULL) {...}


  • 0
    D

    Doing it this way messes up the original linked list. You are changing the label values but you never set them back to what they were before. Instead of an array look at using a map. You can map the old address to the new address. This way you won't modify the original list and it will remain the same after the copy.


Log in to reply
 

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