4
leetCode解题报告之Copy List with Random Pointer
source link: https://blog.csdn.net/ljphhj/article/details/21832129
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
leetCode解题报告之Copy List with Random Pointer_快乐de胖虎-CSDN博客
题目：
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.
分析：我们知道如果是简单的copy List 的话，那么我们只需要从头到尾遍历下来，new出对应个数的Node，并把它们的连接关系设置好就可以了，但是这道题目中每个节点Node出现了Random属性，也就意味着可能当前结点Node所依赖的那个Random对应的结点还没有被创建出来。
解题思路：
为了解决“分析”里提到的问题，我们需要做如下三步处理！
1. 在OldList中的每个结点后，插入一个CopyNode，这个结点的Random域和Next域与OldList中的被拷贝Node的Random域和Next一致，然后让被拷贝结点的Next域指向CopyNode结点，这样先创建出OldList中结点对应的CopyNode结点。
2. 由于所有的CopyNode都已经创建出来了，我们就可以调整这些CopyNode真正的Random域的值了。
3. 调整所有CopyNode的Next域的值，恢复OldList所有Node的Next的值到初始状态！
图解：
AC代码：
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK