leetcode 13：copy-list-with-random-pointer

题目描述

现在有一个这样的链表：链表的每一个节点都附加了一个随机指针，随机指针可能指向链表中的任意一个节点或者指向空。

请对这个链表进行深拷贝。

题目分析：

如果要做到深拷贝，分一下三个步骤：1.分别创建新链表的节点，插入到旧表中 2.根据旧表中的节点复制随机指针 3.剥离旧表和新表，返回新表的头结点。注意指针间的处理即可，属于常规题

代码如下：

RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode* copy;
        RandomListNode* cur;
        if(!head)
            return NULL;
        cur = head;
        //插入旧表中
        while(cur)
        {
            copy = new RandomListNode(cur->label);
            copy->next = cur->next;
            cur->next = copy;
            cur = cur->next->next;
        }
        //复制随机指针
        cur = head;
        while(cur)
        {
            copy = cur->next;
            copy->random = (cur->random?cur->random->next:NULL);
            cur = copy->next;
        }
        //复制的链表从旧表中剥离
        cur = head;
        copy = cur->next;
        head = copy;
        while(cur)
        {
            cur->next = copy->next;
            cur = cur->next;
            copy->next = (cur?cur->next:NULL);
            copy = copy->next;
        }
        return head;
    }