Accepted Java solution with explanation. No additional data structures.


  • 4
    P

    The idea is to use only next and random link of a node to create a copy of list. Please, check sketch and Java code below.

    enter image description here

    public RandomListNode copyRandomList(RandomListNode head) {
    	if (head == null) return null;
    	
    	// Step 1
    	RandomListNode origin = head;
    	while (origin != null) {
    		RandomListNode originNext = origin.next;
    		RandomListNode copy = new RandomListNode(origin.label);
    		origin.next = copy;
    		copy.next = originNext;
    		origin = originNext;
    	}
    	
    	// Step 2
    	origin = head;
    	while (origin != null) {
    		RandomListNode originNext = origin.next.next;
    		RandomListNode copy = origin.next;
    		if (origin.random != null) {
    			copy.random = origin.random.next;
    		} else {
    			copy.random = null;
    		}
    		origin = originNext;
    	}
    	
    	// Step 3
    	origin = head;
    	RandomListNode copyHead = head.next;
    	while (origin != null) {
    		RandomListNode copy = origin.next;
    		RandomListNode originNext = origin.next.next;
    		RandomListNode copyNext;
    		if (copy.next != null) {
    			copyNext = copy.next.next;
    		} else {
    			copyNext = null;
    		}
    		origin.next = originNext;
    		copy.next = copyNext;
    		origin = originNext;
    		copy = copyNext;
    	}
    	
    	return copyHead;
    }
    

  • 0
    C

    Just making the final step a little less convoluted. :)

    public RandomListNode copyRandomList(RandomListNode head) {
            if(head == null)
                return null;
    
            RandomListNode cur = head;
            while(cur != null){
                RandomListNode copy = new RandomListNode(cur.label);
                copy.next = cur.next;
                cur.next = copy;
                cur = cur.next.next;
            }
    
            cur = head;
            while(cur != null){
                if(cur.random != null)
                    cur.next.random = cur.random.next;
                cur = cur.next.next;
            }
    
            cur=head;
            RandomListNode copyHead = new RandomListNode(0), copy = copyHead;
            copyHead.next = cur.next;
            while(cur != null && cur.next!=null){
                copy.next = cur.next;
                copy = copy.next;
                cur.next = cur.next.next;
                cur = cur.next;
            }
    
            return copyHead.next;
        }
    

  • 0
    K
    This post is deleted!

  • 0
    C

    Although the problem statement does not say it, but in actual interview, the interviewer may ask for a solution without modifying original list.
    e.g. make this method threadsafe.


Log in to reply
 

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