JAVA 2ms No map needed.


  • -1
    R
    public RandomListNode copyRandomList(RandomListNode head) {
            if (head == null) return null;
            RandomListNode phantom = new RandomListNode(0);
            RandomListNode current = head;
            RandomListNode newList = phantom;
            newList.next = new RandomListNode(current.label);
            newList = newList.next;
            while(current != null) {
                if (current.next != null) {
                    newList.next = new RandomListNode(current.next.label);
                }
                if (current.random != null) {
                    newList.random = new RandomListNode(current.random.label);
                }
                newList = newList.next;
                current = current.next;
                
            }
            return phantom.next;
        }
    

    Basically iterate through the original list and copy next and random for the new list. I have a feeling I misunderstood the question. Can somebody tell me why is everyone using Map?

    UPDATE: This solution is wrong. I just found out that OJ does not check reference but only value;
    We shouldn't create new Node for random but instead mimic the link.


  • 0
    H

    "...an additional random pointer which could point to any node in the list or null."
    The random pointer should point the node that already exist in the list, while you algo just create many redundant node with the same value


  • 0
    B

    @ratchapong.t

    Leetcode test data is not good enough
    we need care the case where there is one or more circle.
    e.g.
    // 1 -> 2 -> 3 -> 4
    // |<---|
    // |-------->|

        RandomListNode one = new RandomListNode(1);
        RandomListNode two = new RandomListNode(2);
        RandomListNode three = new RandomListNode(3);
        RandomListNode four = new RandomListNode(4);
    
        one.next = two;
        one.random = three;
    
        two.next = one;
        two.random = three;
    
        three.next = four;
    
        RandomListNode copy = copyRandomList(one);

Log in to reply
 

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