8-line one-pass O(N) solution

  • 0

    The solution creates next and random pointers in a single loop together. Keep in mind that, for each node x in original list, the goal is simply to define

    • the cloned node copy[x]
    • the cloned pointers copy[x]->next and copy[x]->random.

    This problem is very similar to clone graph problem.

        RandomListNode *copyRandomList(RandomListNode *h) {
            unordered_map<RandomListNode*, RandomListNode*> copy;
            for (auto x = h; x; x = x->next) 
              if (!copy.count(x)) copy[x] = new RandomListNode(x->label);
              if (x->next)
                copy[x]->next = copy[x->next]? copy[x->next] : copy[x->next] = new RandomListNode(x->next->label);
              if (x->random)
                copy[x]->random = copy[x->random]? copy[x->random] : copy[x->random] = new RandomListNode(x->random->label);                
            return copy[h];

Log in to reply

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