Brilliant Solution with only One Iteration - Using Dummy Node and Dictionary


  • 0
    public RandomListNode CopyRandomList(RandomListNode head)
    {
        if (head == null) return head;
        Dictionary<int, RandomListNode> dic = new Dictionary<int, RandomListNode>();
        RandomListNode Dummy = new RandomListNode(0);
        RandomListNode res = Dummy;
        while (head != null)
        {
            RandomListNode current;
            if (dic.ContainsKey(head.label))
            {
                current = dic[head.label];
            }
            else
            {
                current = new RandomListNode(head.label);
                dic.Add(current.label, current);
            }
            RandomListNode currentrandom;
            if (head.random == null)
            {
                currentrandom = null;
            }
            else if (dic.ContainsKey(head.random.label))
            {
                currentrandom = dic[head.random.label];
            }
            else
            {
                currentrandom = new RandomListNode(head.random.label);
                dic.Add(currentrandom.label, currentrandom);
            }
            res.next = current;
            current.random = currentrandom;
            res = res.next;
            head = head.next;
        }
        return Dummy.next;
    }
    

Log in to reply
 

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