Copy list with random pointer Java O(n) time and o(1) space


  • 0
    /**
     * Definition for singly-linked list with a random pointer.
     * class RandomListNode {
     *     int label;
     *     RandomListNode next, random;
     *     RandomListNode(int x) { this.label = x; }
     * };
     */
    
    
    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            
            if(head==null){
                return head;
            }
            RandomListNode n = head;
            while(n!=null){
                RandomListNode newnode= new RandomListNode(n.label);
                newnode.next=n.next;
                n.next=newnode;
                n=n.next.next;
            }
            n=head;
            while(n!=null){
                if(n.random!=null){
                  n.next.random=n.random.next;
                }
                n=n.next.next;
             
            }
            n=head;
            RandomListNode copy = head.next;
            while(n.next!=null){
                RandomListNode temp = n.next;
                n.next=n.next.next;
                n=temp;           
            }
    
            
           return copy;
            
        }
    }
    
    

Log in to reply
 

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