# 138 Copy List with Random Pointer

這題要把一個除了正常的next pointer之外，還多了random pointer的linked list拷貝一份。

做法分成三步驟：

1. 把每個node都複製一份(只複製value，先不管random pointer)，把複製品接在本尊的後面
2. 把複製品的random pointer也接好
3. 把複製品們取出來，並把原本的linked list重建回去

這麼一來就不用另外用個hash table把每個node的random pointer指向誰記起來了～

完整程式碼：

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        //copy all nodes and link each copy after the original node
        //link random pointers for each copy node
        //restore original list
        RandomListNode cur = head;
        while(cur != null){
            RandomListNode copy = new RandomListNode(cur.label);
            copy.next = cur.next;
            cur.next = copy;
            cur = cur.next.next;
        }

        cur = head;
        while(cur!=null){
            if(cur.random!=null)
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }

        cur = head;
        RandomListNode cHead = new RandomListNode(0);
        RandomListNode copyCur = cHead, copy;
        while(cur!=null){
            //extract copy
            copy = cur.next;
            copyCur.next = copy;
            copyCur = copy;

            //restore
            cur.next = cur.next.next;
            cur = cur.next;
        }

        return cHead.next;
    }
}