C++ simple recursive solution


  • 0
    E

    This is my simple recursive code.

    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            if(!head) return head;
            
            RandomListNode *newnode = new RandomListNode(head->label);
            
            if(head->random)
            newnode->random = new RandomListNode(head->random->label);
            
            newnode->next = copyRandomList(head->next);
            return newnode;
        }
    };
    

  • 0
    W

    Hi, I think your code might exist some problems.
    In you code, the random pointer points a to a new space, which is irrelevant to the new linked list. But I think the address of the random pointer and the corresponding node in a linked list should be the same.

    For example: A random linked list. 1 -> 2 -> nullptr ( 1's random pointer also points at 2.). In this case, 1's random pointer's address should be the same as the address of the node whose label is 2.


  • 0
    E

    Well, yes you're right. I didn't consider the situation you mentioned. The code was accepted and I thought it is right. Thank you for pointing out this mistake. Do you know how to rectify the recursive method ? I didn't come up with a right answer using recursion.


  • 0
    W

    @euphoriaa
    Hi. My solution is to use two maps to store all info of the linked list and make a deep copy by the order(index) in the map to ensure the same reference.
    For recursive method, Sorry I'm not proficient in it. :) I think the assignment of the random pointer should be after completion of the construction of a linked list.(But also need other info to record the index.)

    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            if(!head) return head;
            
            RandomListNode *newnode = new RandomListNode(head->label);
            
            newnode->next = copyRandomList(head->next);
    
            // need other manipulations to find the exact index of the random pointer
            // with the help of pointer:head.
            newnode->random = ptr; 
            return newnode;
        }
    };
    

    hope it helps you! :)


  • 0
    E

    @wysqh Hi, thanks for your help! !


Log in to reply
 

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