Verbose 3-Pass Java Solution with Explaination


  • 0

    0_1491779148368_14917790308337.png

    Idea shown as above: each origin's random will be modified to point to new node. And need a temp list to backup origin list's random pointers. Here is the code with some comments:

        public RandomListNode copyRandomList(RandomListNode head) {
            if(head==null)
                return null;
            
            RandomListNode newHead = new RandomListNode(head.label);
            newHead.random = head.random;
            
            RandomListNode tempHead = new RandomListNode(head.label);
            tempHead.random = head.random;  // backup original node's random reference in temp node
        
            head.random = newHead;  // modify original node's random to new copied node
                
            RandomListNode originNode = head.next;
            RandomListNode tempNode = tempHead;
            RandomListNode node = newHead;
            while(originNode!=null) {
                node.next = new RandomListNode(originNode.label);
                node = node.next;
                node.random = originNode.random;
                
                tempNode.next = new RandomListNode(originNode.label);
                tempNode = tempNode.next;
                tempNode.random = originNode.random;  // backup original node's random reference in temp node
                
                originNode.random = node;  // modify original node's random to new copied node
                
                originNode = originNode.next;
            }
            
            // Link new copied node's random references to existing new created nodes.
            node = newHead;
            while(node!=null) {
                node.random = node.random != null ? node.random.random : null;
                node = node.next;
            }
            
            // Recover original node's random references
            tempNode = tempHead;
            originNode = head;
            while(tempNode!=null) {
                originNode.random = tempNode.random;
                tempNode.random = null; // clear temp reference to original node so that original nodes can be GCed if possible
                tempNode = tempNode.next;
                originNode = originNode.next;
            }
            
            // tempNodes will be cleared afterwards
            
            return newHead;
        }

Log in to reply
 

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