Java Solution without using hashmap: O(n2), still accepted in first try :)


  • 0
    C
    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            RandomListNode head1 = null;
            if(head != null){
                head1 = copy(head);
                RandomListNode origHead1 = head;
                RandomListNode origHead2 = head1;
                while(head1 != null){
                    if(head1.random != null){
                        head1.random = findRandom(origHead1,origHead2,head1.random);
                    }
                    head1 = head1.next;
                }
                head1 = origHead2;
            }
            return head1;
        }
        
        private static RandomListNode findRandom(RandomListNode head1,RandomListNode head2,RandomListNode node){
            if(node == head1){
                return head2;
            }else if(head1.next != null){
                return findRandom(head1.next,head2.next,node);
            }else
                return null;
        }
        
        private static RandomListNode copy(RandomListNode node){
            if(node == null)
                return null;
            RandomListNode next = copy(node.next);
            RandomListNode head = new RandomListNode(node.label);
            head.next = next;
            head.random = node.random;
            return head;
        }
        
    }
    

Log in to reply
 

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