Shortest java O(1) space, why we need a map?


  • 0
    J
    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            if(head==null)return null;
            RandomListNode first=head;
            RandomListNode nHead=new RandomListNode(first.label);
            RandomListNode second=nHead;
            while(first!=null)
            {
            	if(first.next!=null)second.next=new RandomListNode(first.next.label);//copy next
            	else second.next=null;
            	
            	if(first.random!=null)second.random=new RandomListNode(first.random.label);//copy random
            	else second.random=null;
            	first=first.next;
            	second=second.next;
            }
            return nHead;
        }
    }
    
    

    Why this question need a map?I think it is a very obvious and straightforward, my code pass the submission. is it wrong?


  • 0

    Good one to copy "next" pointer, but not perfect one to copy "random" pointer.

    Let's say you have a linked list, for Next pointer : 1 => 2 => 3
    but for Random pointer: 1 = > 2 <= 3 (1 points to 2, 2 points to null, 3 points to 2)
    Totally 3 nodes.

    What you are asked to do is return this:
    1 => 2 => 3 (=> for Next Pointer)
    ↓___↑____↓ (— for Random Pointer)

    You do copy Next pointer correctly 1 => 2 => 3, but for Random Pointer. You actaully created additionally 2 Nodes with value 2.
    1 => 2 => 3
    ↓ xxxxxxx ↓
    2 xxxxxxx 2

    Random Pointers of Node 1 and Node 3 point to another 2 nodes with value 2. Even though their values are the same, they are not the same Object.

    If you do not understand this, try start with E and M difficulty and get familiar with Java first.


  • 0
    C

    In short, you are creating extra nodes equal to the number of non-null random pointers.
    Your solution passes, because it's impossible for LeetCode to detect that extra space. However your interviewer won't fail to detect that :)


Log in to reply
 

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