JAVA code with O(n) complexity but takes 366ms and needs three iterations. Any improvement?


  • 1
    N

    public RandomListNode copyRandomList(RandomListNode head) {

        if( head == null)
        {
            return null;
        }
        RandomListNode temp = head;
        
        while(temp != null)  
        {
            RandomListNode var = new RandomListNode(temp.label);
            var.next = temp.next;
            var.random = null;
            temp.next = var;
            temp = temp.next.next;
        }
        
        temp = head;
        
        while(temp != null) // linking the random pointer of the newly added nodes
        { 
            if(temp.random != null)
            {
                temp.next.random = temp.random.next;
            }
            
            temp = temp.next.next;
        }
        // now separating out the alternate node
        
        RandomListNode new_head = null, new_temp= null;
        
        temp = head;
        while(temp != null)
        {
            if(new_head == null)
            {
                new_head = temp.next;
                new_temp = new_head;
            }
            else
            {
                new_temp.next = temp.next;
                new_temp = new_temp.next;
            }
                temp.next = temp.next.next;
                temp = temp.next;
        }
        return new_head;
    }

Log in to reply
 

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