Verbose 3-Pass Java Solution with Explaination

  • 0


    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) {
                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 =;
            RandomListNode tempNode = tempHead;
            RandomListNode node = newHead;
            while(originNode!=null) {
       = new RandomListNode(originNode.label);
                node =;
                node.random = originNode.random;
       = new RandomListNode(originNode.label);
                tempNode =;
                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 =;
            // 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 =;
            // 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 =;
                originNode =;
            // 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.