I am facing problem in https://oj.leetcode.com/problems/copy-list-with-random-pointer


  • 0
    R

    Below is my code:

    /**
     * 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) {
            if(head==NULL){
                return head;
            }
            RandomListNode* start=NULL;
            RandomListNode* t=head;
            RandomListNode* begin=NULL;
            int f=0;
            while(t!=NULL){
                if(begin==NULL){
                    begin=new RandomListNode(t->label);
                }
                begin->random=t;
                RandomListNode* st=t->next;
                t->next=begin;
                t=st;
                if(f==0){
                    start=begin;
                    f=1;
                }
                
                begin=begin->next;
                
            }
            begin=start;
            t=head;
            while(begin!=NULL){
                if(begin->random->random!=NULL)
                    begin->random=begin->random->random->next;
                else begin->random=NULL;
                if(begin->next!=NULL)
                    t->next=begin->next->random;
                else t->next=NULL;
                t=t->next;
                begin=begin->next;
            }
            return start;
        }
    };
    

    Output:

    Input:  {-1,1,#,#}
    Output: Next pointer of node with label -1 from the original list was modified.
    Expected:   {-1,1,#,#}
    

    Can someone point out where the bug is ?


  • 0
    S

    I guess I see the problem
    In your first whileLoop where you are creating duplicateList which you are iterating with begin,
    you are not linking its nodes. Basically you need to keep a pointer for last createdNode whose next should point to newly created node.


  • 0
    N

    Your code change every "next" element of node in original list to the node of new create list


Log in to reply
 

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