原题链接 思路：
这道题直观的看起来甚至不需要什么算法，就按照一般的复制思路，新开辟空间，然后把对应的节点的值抄过去，先不看random。令人头疼的是Node->random是随意指向的，没有什么规律可以遵循。于是想到将每个节点的random相对于头节点的偏移量找出来，在新的链表中对应的偏移量找到random节点，指向即可。起初以为这样做会超时，但结果还好，时间54%，内存60%。不好的一点是用了很多指针表示位置，有些乱，思路简单是要付出代价的呵呵呵呵。 给出代码： /* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { if(head == NULL) return NULL; Node* current = NULL; current = head; Node *result = NULL; Node *newHead = NULL; result = new Node(head->val); newHead = result; while(current != NULL){ Node* midNode = new Node(-1); if(current->next != NULL){ result->next = midNode; } result->val = current->val; current = current->next; result = result->next; } current = head; result = newHead; Node *subRandom; Node *oldCurrent; oldCurrent = head; subRandom = newHead; while(current != NULL){ if(current->random == NULL){ subRandom->random = NULL; }else{ int i = 0; Node *subCurrent; subCurrent = current->random; while(oldCurrent != subCurrent){ //在这里找当前节点的random的偏移量 i++; oldCurrent = oldCurrent->next; } while(i>0){ //去找新链表中的对应偏移量下的节点 result = result->next; i--; } subRandom->random = result; } subRandom = subRandom->next; result = newHead; current = current->next; oldCurrent = head; } return newHead; } };≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈新方法学习≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈≈ 一、看评论中的解题方法，比较先进的是使用了 unordered_map 使用映射方式减少了大量遍历开销
二、当然有剑指Offer书上的方法 对此方法的描述是：
将原链表的每个节点后面复制一个与该节点一样的节点，破坏了原来的链表结构。表明，相邻重复元素，第一个是旧元素，后一个是新元素。在新构成的长链表上，利用原来的链表中的random关系，将每个新节点的random设置一下。恢复原链表，将所有新节点从长链表上切下来构成复制成功的链表。 这种思想实在值得学习！！！