@@ -0,0 +1,2931 @@
+/*%0A * Key point: %0A *      1.common solution: insert a copy after each %0A *        original node(ignore random pointer now), then copy random pointer,%0A *        finally, split the original list and copied list%0A *%0A *      2.HashMap Solution: use a HashMap%3CRandomListNode,RandomListNode%3E to %0A *        construct a key value pair between original node and new copied node,%0A *        then, copy the next and random pointer accordingly%0A */%0A%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 */%0Apublic class Solution %7B%0A    public RandomListNode copyRandomList(RandomListNode head) %7B%0A        if(head == null)%0A            return head;%0A            %0A        //insert a copy after each original node (ignore random pointer now)    %0A        RandomListNode current = head;    %0A        while(current != null)%7B%0A            RandomListNode copy = new RandomListNode(current.label);%0A            copy.next = current.next;%0A            current.next = copy;%0A            current = current.next.next;%0A        %7D%0A        %0A        //copy random pointer%0A        current = head;%0A        while(current != null)%7B%0A%0A            if(current.random != null) //take care, random pointer may be null%0A                current.next.random = current.random.next;%0A            else%0A                current.next.random = null;%0A                %0A            current = current.next.next;%0A        %7D%0A        %0A        //split original list and copy list%0A        current = head;%0A        RandomListNode newHead = current.next;%0A        RandomListNode newCurrent = newHead;%0A        while(newCurrent != null)%7B%0A            current.next = newCurrent.next;%0A            %0A            if(newCurrent.next != null)%0A                newCurrent.next = newCurrent.next.next;%0A            %0A            current = current.next;%0A            newCurrent = newCurrent.next;%0A        %7D%0A        %0A        return newHead;%0A    %7D%0A%7D%0A%0A/*%0A * HashMap Solution%0A */%0A%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 */%0Apublic class Solution %7B%0A    public RandomListNode copyRandomList(RandomListNode head) %7B%0A        if(head == null)%0A            return head;%0A        %0A        HashMap%3CRandomListNode, RandomListNode%3E hm = new HashMap%3CRandomListNode, RandomListNode%3E();%0A        RandomListNode current = head;%0A        while(current != null)%7B%0A            hm.put(current, new RandomListNode(current.label));%0A            current = current.next;%0A        %7D%0A        %0A        current = head;%0A        while(current != null)%7B%0A            hm.get(current).next = hm.get(current.next);%0A            hm.get(current).random = hm.get(current.random);%0A            current = current.next;%0A        %7D%0A        %0A        return hm.get(head);%0A    %7D%0A%7D

Copy List with Random Pointer