题目大意
一个链表中的每一个节点都有一个额外的随机指针，指向链表中的任意节点或空节点。对这个链表进行深拷贝。（要拷贝随即指针）
解题思路
有两种思路，参考：
http://bookshadow.com/weblog/2015/07/31/leetcode-copy-list-random-pointer/
https://shenjie1993.gitbooks.io/leetcode-python/138%20Copy%20List%20with%20Random%20Pointer.html
这里只写一种思路：链表的拷贝其实可以看做两个步骤，一个是节点数据的拷贝，另一个是节点关系的拷贝。我们也可以先把所有的节点进行拷贝，并存入字典中。然后遍历链表并拷贝两个指针。因为任意指针可能指向空指针，所以在字典中添加一个空指针项。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
if not head:
return None
visited = dict()
# 复制值
node = head
while node:
visited[node] = RandomListNode(node.label)
node = node.next
# 给一个空值
visited[None] = None
# 复制关系
node = head
while node:
visited[node].next = visited[node.next]
visited[node].random = visited[node.random]
node = node.next
return visited[head]
|
总结