No HashMap O(n) Java solution


  • 2
    R

    The idea is the same to the others. It needs to iterate the original list three times.
    The in-text annotation should be more helpful

    public class Solution {
            public RandomListNode copyRandomList(RandomListNode head) {
                
                if (head==null) return null;
                
                RandomListNode node = head;
                //1. In-place copy: Copy new code, insert to the next position of original code
                
                while(node!=null){
                    RandomListNode temp = new RandomListNode(node.label);//Copy
                    //Insert
                    temp.next=node.next;
                    node.next=temp;
                    //Move
                    node=temp.next;
                }
                
                //2. Assign the random
                node=head;
                while(node!=null){
                    if (node.random!=null)node.next.random=node.random.next;
                    node=node.next.next;
                }
                //3.Split the sequence
                RandomListNode ori = head;
                RandomListNode nova = head.next;
                node = head.next;
                
                while(ori!=null){
                    //Split
                    ori.next=ori.next.next;
                    if (nova.next!=null) nova.next=nova.next.next;
                    //Move
                    ori=ori.next;
                    nova=nova.next;
                }
                return node;
                
            }
        }

  • 0
    A

    I also didn't use hashMap, and only use one while loop, but time is 500+

    public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) {
            return null;
        }
        RandomListNode result = new RandomListNode(head.label);
        RandomListNode curr1 = head;
        RandomListNode curr2 = result;
        
        while(curr1 != null ) {
            if(curr1.next != null) {
                curr2.next = new RandomListNode(curr1.next.label);
            }
            
            if(curr1.random != null) {
                curr2.random = new RandomListNode(curr1.random.label);
            }
            curr1 = curr1.next;
            curr2 = curr2.next;
        }
        return result;
    }
    

    }


  • 0
    J

    Your answer is not correct, random pointer may just points to another node in the linked list.

    Consider this example:

    | |>
    1 -> 2 -> 3 -> NULL
    ^ |
    | |
    -------

    i.e. 1's random points to 2, 3' s random points to 2.
    Try to run your code see what would happen.


  • 0
    J

    = =! my example is collapsed, let me describe: 1's next points to 2, 1's random points to 2; 2's next points to 3, 2's random is null; 3's next points to null, 3's random points to 2.


  • 0
    A

    I know what you mean. In your case, 2 is already there, when 1 randomly points to it again, I create another new node instead of previous one(2 in this case), when 3 randomly points to 2, I also create new node, but I should let 1 and 3 randomly point to 2, this means there should be only one 2's node..
    Do you think I understand what you said? Thanks! I think my code is not correct, but it passed all the test, it is weird...


Log in to reply
 

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