新加坡网站后缀/百度关键词搜索指数
九章算法官网-原文网址
http://www.jiuzhang.com/problem/57/
题目
给出一条带随机指针的链表，对其进行深度拷贝(Deep Copy)。
带随机指针的意思是，对于每个节点，除了next指针指向下一个节点以外，还带一个randomNext指针指向任何一个链表中的节点或空。
深度拷贝的意思是，对于新复制出来的链表，是一条完全独立于原来链表的链表，对于这个新的链表进行任何操作都不会对原来的链表产生影响。
Follow Up Question: 如果不能使用额外的辅助空间，算法该如何设计？
在线测试本题
http://www.lintcode.com/zh-cn/problem/copy-list-with-random-pointer/
解答
第一步：使用HashMap，首先复制所有的节点，用HashMap记录老节点A与新节点A'的映射关系。
第二步：遍历每个点，将Random指针连上。如存在一条Random指针从A指向B，那么在HashMap中找到映射的新节点A'和B'，将A'的Random指针指向B'。
额外空间复杂度O(n)，时间复杂度O(n)
Follow Up 如果不适用额外的辅助存储空间：
第一步：将每个节点复制并插入相邻节点中。如1->2->3->NULL变为：1->1'->2->2'->3->3'->NULL。
第二步：接下来连接Random指针，如果存在一条Random指针从A指向B，那么将A->next的Random指针指向B->next。
第三步：将链表拆开。A=head, A'=head->next; A->next=A->next->next；A'->next=A'->next->next; ...
时间复杂度O(n)，额外空间复杂度O(1)