@@ -0,0 +1,2585 @@
+package leetcode131_140;%0A%0Aimport java.util.HashMap;%0Aimport java.util.LinkedList;%0Aimport java.util.Map;%0Aimport java.util.Queue;%0A%0A/**A linked list is given such that each node contains an additional random pointer%0A which could point to any node in the list or null. Return a deep copy of the list.%0A * Created by eugene on 16/2/26.%0A */%0Apublic class CopyListWithRandomPointer %7B%0A%0A    //Definition for singly-linked list with a random pointer.%0A    class RandomListNode %7B%0A        int label;%0A        RandomListNode next, random;%0A        RandomListNode(int x) %7B this.label = x; %7D%0A    %7D;%0A%0A    //%E4%BB%85%E4%BD%BF%E7%94%A8%E5%93%88%E5%B8%8C%E8%A1%A8%E5%92%8C%E5%8F%8C%E6%8C%87%E9%92%88,%E9%80%9F%E5%BA%A6%E6%9B%B4%E5%BF%AB%0A    public RandomListNode copyRandomList(RandomListNode head) %7B%0A        if (head==null) return null;%0A        Map%3CRandomListNode, RandomListNode%3E map = new HashMap%3C%3E();%0A        RandomListNode newHead = new RandomListNode(head.label);%0A        RandomListNode p = head;%0A        RandomListNode q = newHead;%0A        map.put(head, newHead);%0A        p = p.next;%0A        while (p!=null)%7B%0A            RandomListNode newNode = new RandomListNode(p.label);%0A            map.put(p, newNode);%0A            q.next = newNode;%0A            q = newNode;%0A            p = p.next;%0A        %7D%0A        p = head;%0A        q = newHead;%0A        while (p!=null)%7B%0A            if (p.random!=null) q.random = map.get(p.random);%0A            p = p.next;%0A            q = q.next;%0A        %7D%0A        return newHead;%0A    %7D%0A%0A    //%E4%B8%8EClone Graph%E6%80%9D%E8%B7%AF%E4%B8%80%E8%87%B4,%E4%BD%BF%E7%94%A8%E9%98%9F%E5%88%97%E5%92%8C%E5%93%88%E5%B8%8C%E8%A1%A8%0A    public RandomListNode copyRandomList1(RandomListNode head) %7B%0A        if (head==null) return null;%0A        Map%3CRandomListNode, RandomListNode%3E map = new HashMap%3C%3E();%0A        Queue%3CRandomListNode%3E queue = new LinkedList%3C%3E();%0A        queue.offer(head);%0A        RandomListNode newHead = new RandomListNode(head.label);%0A        map.put(head, newHead);%0A        while (!queue.isEmpty())%7B%0A            RandomListNode curOld = queue.poll();%0A            RandomListNode%5B%5D olds = %7BcurOld.next, curOld.random%7D;%0A            for (int i=0; i%3C2; i++)%7B%0A                if (olds%5Bi%5D==null) continue;%0A                if (!map.containsKey(olds%5Bi%5D))%7B%0A                    RandomListNode newNode = new RandomListNode(olds%5Bi%5D.label);%0A                    map.put(olds%5Bi%5D, newNode);%0A                    if (i==0) map.get(curOld).next = newNode;%0A                    else map.get(curOld).random = newNode;%0A                    queue.offer(olds%5Bi%5D);%0A                %7D else %7B%0A                    if (i==0) map.get(curOld).next = map.get(curOld.next);%0A                    else map.get(curOld).random = map.get(curOld.random);%0A                %7D%0A            %7D%0A        %7D%0A        return newHead;%0A    %7D%0A%0A%7D%0A

Copy List with Random Pointer