# 138 Copy List with Random Pointer

這個題目要求copy一份有random pointer的linked list。

直接copy是不可行的，因為copy過去的node會指向原本的linked list。

所以要創一個新的linked list，再把原linked list的指針怎麼指 一一copy過去。

最基本的做法是用hash table把每個node要連接的對象記錄起來，再重建。

LeetCode上有個聰明做法，三個步驟：

1. 在所有node後面都分別接上一份copy，copy和前一個node的label相同， 原本1->2->3->4變成1->1->2->2->3->3->4->4
2. 在這個新的linked list上iterate，分別把copy node們的random pointer接上，
3. 最後再取出copy node們，並重建原本的linked list。重建時需要三個指針，一個給原linked list，另一個給copy linked list，還要一個記錄copy linked list的頭。

完整程式碼如下：

/**
 * 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;
        while(cur!=null){
            //extract copy
            copyCur.next = cur.next;
            copyCur = cur.next;

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

        return cHead.next;
    }
}