[closed] Copy List with Random Pointer

Question

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list. oj.leetcode.com/problems/copy-list-with-random-pointer/

My code seems fine but is giving a runtime error

Blockquote

/**
 * 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 *t = head, *ans, *tmp ;
        while(head){
            RandomListNode *node = new RandomListNode(head->label) ;
            node->next = head->random ;
            head->random = node ;
            head = head->next ;
        }
        head = t ;
        while(head){
            tmp = head->random ;
            if(tmp->next)
                tmp->random = tmp->next->random ;
            head = head->next ;
        }
        head = t ;
        ans = head->random ;
        while(head){
            tmp = head->random ;
            head->random = tmp->next ;
            if(head->next){
                tmp->next = head->next->random ;
            }else{
                tmp->next = NULL ;
            }
            head = head->next ;
        }
        return ans ;
    }
};

Blockquote

Answer 1

Hi wrathtoliar, you should check tmp(tmp = head->random ; The correct code is here.Please let me know if you have optimized solution. This is O(n) with three iteraions.


class Solution {
public:
    RandomListNode copyRandomList(RandomListNode head) {
        if(!head)
           return head;
        RandomListNode current=head;
        RandomListNode nextNode;
        while(current){
            nextNode=current->next;
            current->next=new RandomListNode(current->label);
            current->next->next=nextNode;
            current=current->next->next;
        }
        current=head;
        while(current){
            if(current->random)
            current->next->random=current->random->next;
            current=current->next->next;
        }
        current=head;
        RandomListNode copy=current->next;
        RandomListNode currentcopy=copy;
        while(current->next->next){
            current->next=current->next->next;
            currentcopy->next=currentcopy->next->next;
            current=current->next;
            currentcopy=currentcopy->next;
        }
        current->next=NULL;
    return copy;
    // Note: The Solution object is instantiated only once and is reused by each test case.

}

};

Answer 2

RandomListNode *copyRandomList(RandomListNode *head) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    if(head==NULL) return NULL;
    unordered_map<RandomListNode*,RandomListNode*> node_map;
    RandomListNode *n=head,*copyn=new RandomListNode(head->label),*nextn,*randn;
    node_map[n]=copyn;
    while(n!=NULL){
        randn=n->random;
        if(randn!=NULL){
            if(node_map.count(randn)==0){
                RandomListNode *randcopyn=new RandomListNode(randn->label);
                node_map[randn]=randcopyn;
                copyn->random=randcopyn;
            }
            else{
                copyn->random=node_map[randn];
            }
        }
        nextn=n->next;
        if(nextn!=NULL){
            if(node_map.count(nextn)==0){
                RandomListNode *nextcopyn=new RandomListNode(nextn->label);
                node_map[nextn]=nextcopyn;
                copyn->next=nextcopyn;
                copyn=nextcopyn;
            }
            else{
                copyn->next=node_map[nextn];
                copyn=node_map[nextn];
            }
        }
        n=nextn;
    }
    return node_map[head];
}

Answer 3

I use the depth first search scheme to solve this problem with a map.

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if( head==NULL ) return NULL;
        RandomListNode* newHead = NULL;
        unordered_map< RandomListNode*, RandomListNode* > occur;
        dfs( newHead, head, occur );
        return newHead;
    }
    void dfs( RandomListNode*&cur, RandomListNode* node, unordered_map<RandomListNode*, RandomListNode* >& occur ){
        if( node==NULL ) return;
        cur = new RandomListNode( node->label );
        if( occur.find(node) == occur.end() ){
            occur[node] = cur;
        }
        if( node->next ){
            if( occur.find(node->next)==occur.end() ){
                dfs( cur->next, node->next, occur );
            }else{
                cur->next = occur[node->next];
            }
        }
        if( node->random ){
            if( occur.find(node->random)==occur.end() ){
                dfs( cur->random, node->random, occur );
            }else{
                cur->random = occur[node->random];
            }
        }
    }
};

[closed] Copy List with Random Pointer

The question has been closed for the following reason "bulk close" by 1337c0d3r 25 Oct, 06:25

Follow this question

Welcome to LeetCode

Related questions