My solution in Java


  • 0
    A

    The key of my solution is using map for the relation between the given list and the new list.

    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
            if(head==null) return head;
            RandomListNode copyHead=new RandomListNode(0);
            RandomListNode first=new RandomListNode(0);
            RandomListNode cur=head;
            RandomListNode nxt=null;
            first.next=copyHead;
            HashMap<RandomListNode,RandomListNode> map=new HashMap<RandomListNode,RandomListNode>();
            HashMap<RandomListNode,RandomListNode> map1=new HashMap<RandomListNode,RandomListNode>();
            while(cur!=null)
            {
                nxt=cur.next;
                RandomListNode temp=new RandomListNode(cur.label);
                if(cur.random!=null) map.put(temp,cur.random);
                map1.put(cur,temp);
                copyHead.next=temp;
                copyHead=copyHead.next;
                cur=nxt;
            }
            cur=first.next.next;
            while(cur!=null)
            {
                if(map.get(cur)!=null)
                {
                    cur.random=map1.get(map.get(cur));
                }
                cur=cur.next;
            }
            return first.next.next;
        }
    }

Log in to reply
 

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