Accepted O(n) time O(1) space Java solution with only 1 while loop. 15 lines


  • -1

    My solution builds the deep copy list at the same time its iterating through the original list, which allows me to only use one while loop. The following steps are taken to build the deep copy. First a copy of the original head is created(newHead). At this time we now have a copy of the original head, its next pointer, and its random pointer.Note the next pointer and the random pointer nodes are incomplete the node only has content in the label field. We then create a walking stick pointer (ws) so we don't lose our new head. The content (label) in our ws is the same as the element our original head reference points to; however the next, and the random pointers are currently null. To fix this we copy the next and random pointer from head and assign it to ws. This process is continued until the end of the original list is reached.

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        
        RandomListNode newHead = new RandomListNode(head.label);
        addNextAndRandom(head, newHead);
        RandomListNode ws = newHead.next;
        head = head.next;
        while (head != null) {
            addNextAndRandom(head, ws);
            ws = ws.next;
            head = head.next;
        }
        return newHead;
    }
    
    private void addNextAndRandom(RandomListNode oldNode, RandomListNode newNode) {
        newNode.next = oldNode.next == null ? null : new RandomListNode(oldNode.next.label);
        newNode.random = oldNode.random == null ? null : new RandomListNode(oldNode.random.label);
    }

  • 0
    L

    You always create a new node for new node's random. But actually the random node is pointed to an existing node rather than a new node. Although your code can pass the test cases, it may not be correct.


Log in to reply
 

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