A 11-Line C# Time O(N) Space O(N) Solution -- 124ms


  • 0
    L
    public RandomListNode CopyRandomList(RandomListNode head) {
        if(head == null) return null;
        Dictionary<RandomListNode, RandomListNode> map = new Dictionary<RandomListNode, RandomListNode>();
        RandomListNode cpHead = new RandomListNode(head.label);
        map.Add(head, cpHead);
        for(RandomListNode cur = head.next, cpLst = cpHead; cur != null; cur = cur.next, cpLst = cpLst.next){
            cpLst.next = new RandomListNode(cur.label);
            map.Add(cur, cpLst.next);
        }
        for(RandomListNode cur = head, cpCur = cpHead; cur != null; cur = cur.next, cpCur = cpCur.next)
            cpCur.random = cur.random == null ? null : map[cur.random];
        return cpHead;
    }

  • 0
    D

    if the solution use the O(n) space map,may be we can use the recursive to make the code simpler

      class Solution {
        map<int,RandomListNode *> m; 
        public:
            RandomListNode *copyRandomList(RandomListNode *head) {
                if(!head) return NULL;
                if(m.find(head->label)==m.end()){
                    m[head->label] = new RandomListNode(head->label);
                    m[head->label]->next = copyRandomList(head->next);
                    m[head->label]->random = copyRandomList(head->random);
                }
                return m[head->label];
            }
        };

Log in to reply
 

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