two O(n) solutions, with map & without map


  • 0
    M
    
        public RandomListNode copyRandomList_noMap(RandomListNode head) {
            if(head==null) return null;
            //copy
            RandomListNode p = head;
            while(p!=null){
                RandomListNode oldNext = p.next;
                RandomListNode newNode = new RandomListNode(p.label);
                p.next = newNode;
                newNode.next = oldNext;
                p = oldNext;
            }
            //set random
            p = head;
            while(p!=null){
                RandomListNode oldRand = p.random;
                RandomListNode newRand = (oldRand==null ? null : oldRand.next);
                p.next.random = newRand;
                p = p.next.next;
            }
            //split
            RandomListNode fakeHead = new RandomListNode(0);
            RandomListNode cur = fakeHead;
            p = head;
            while(p!=null){
                RandomListNode oldNext = p.next.next;
                cur.next = p.next;
                cur = cur.next;
                p.next = oldNext;
                p = oldNext;
            }
            return fakeHead.next;
        }
    
        public RandomListNode copyRandomList_map(RandomListNode head) {
            if(head==null) return null;
            Map<RandomListNode, RandomListNode> map = new HashMap<>();
            RandomListNode fakeHead = new RandomListNode(0);
            for(RandomListNode p=head, pre=fakeHead; p!=null; p=p.next){
                RandomListNode cur = new RandomListNode(p.label);
                pre.next = cur;
                pre = cur;
                map.put(p, cur);
            }
            for(RandomListNode p=head; p!=null; p=p.next){
                RandomListNode newNode = map.get(p);
                RandomListNode newRandNode = map.get(p.random);
                newNode.random = newRandNode;
            }
            return fakeHead.next;
        }
    

Log in to reply
 

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