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.
最先想到就是遍历列表生成新的列表，但没有对random域进行赋值。在遍历一次列表，然后进行random域赋值。但其存在一个问题，就是进行random赋值的时候需要耗费时间久，因为random域没有规律可循，需要进行遍历列表，也就是时间复杂度为O(N^2)。后面发现一个方法，就是通过对每个列表节点进行double，然后在进行random域的复制就变得有规律可循：
1.将列表内的节点全部复制，并连接在原节点后面
2.对新的节点的random域进行赋值，新节点.random = 原节点.random.next
3.将新节点从列表中抽离出新的列表
代码如下：
/** * Definition for singly-linked list with a random pointer. * struct RandomListNode { * int label; * RandomListNode *next, *random; * RandomListNode(int x) : label(x), next(NULL), random(NULL) {} * }; */ class Solution { public: RandomListNode *copyRandomList(RandomListNode *head) { RandomListNode* next,*cur; cur = head; while(cur) { next = cur->next; RandomListNode* tmp = new RandomListNode(cur->label); tmp->next = next; cur->next = tmp; cur = next; } cur = head; while(cur) { next = cur->next; if(cur->random) next->random = cur->random->next; else next->random = cur->random; cur = next->next; } RandomListNode* result = new RandomListNode(0); RandomListNode* copy,*copyCur=result; cur = head; while(cur) { next = cur->next->next; copyCur->next = cur->next; copyCur = copyCur->next; cur->next = next; cur = cur->next; } return result->next; } };
