Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

http://www.lintcode.com/en/problem/copy-list-with-random-pointer/

Solution

1. copy nodes,insert them
2. assign random pointer
3. split it into to lists, one is the original , the other is the copy.

画个草图就理解了。拷贝以后，assing random pointer比较有技巧，copied.random = origianl.random，要保证能拆分嘛，当然要找到origianl.random在copy链表里对应的node，origianl.random.next。这里非常巧妙，因为origianl.random.next就是原链表中的random。

class Solution {
public:
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    RandomListNode *copyRandomList(RandomListNode *head) {
        // write your code here
        RandomListNode *cur = head;
        while (cur != NULL) {//copy nodes,每个copy节点都插入到远节点的后面
            RandomListNode *nt = cur->next;
            RandomListNode *newnode = new RandomListNode(cur->label);
            newnode->next = cur->next;
            cur->next = newnode;
            cur = nt;
        }
        cur = head;
        while(cur != NULL) {//assin random pointer
            RandomListNode *nt = cur->next;
            if(cur->random != NULL)
                nt->random = cur->random->next;
            cur = nt->next;
        }
        cur = head;
        RandomListNode *copy = (head==NULL) ? NULL:head->next;
        while(cur != NULL) {//将copy链表拆分出来
            RandomListNode *nt = cur->next;
            cur->next = nt->next;
            if(nt->next != NULL)
                 nt->next = nt->next->next;
            cur = cur->next;
        }
        return copy;
    }
};