给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深度拷贝。
Solution 1
构建一个dict，存储{label：[node,...]}，作为random的检索基础
然后构建一个list，顺序存储所有random指向的节点在dict中位置，[(label, pos), None, ...]，然后建立新链表，random不赋值
然后再新链表上再次构建dict同上，最后顺序遍历list，取出相关位置，并让random指向对应的新节点
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
node_dict = {}
p = head
random_list = []
dummy = RandomListNode(0)
pp = dummy
while p:
if p.label not in node_dict:
node_dict[p.label] = []
node_dict[p.label].append(p)
pp.next = RandomListNode(p.label)
pp = pp.next
p = p.next
p = head
while p:
temp = None
if p.random:
for i, _node in enumerate(node_dict[p.random.label]):
if p.random is _node:
temp = (p.random.label, i)
random_list.append(temp)
p = p.next
pp = dummy.next
node_dict = {}
while pp:
if pp.label not in node_dict:
node_dict[pp.label] = []
node_dict[pp.label].append(pp)
pp = pp.next
pp = dummy.next
i = 0
while pp:
temp = random_list[i]
if temp:
pp.random = node_dict[temp[0]][temp[1]]
else:
pp.random = None
pp = pp.next
i += 1
return dummy.next
Solution 2
1）建立新节点，每个新节点插在旧节点的后面
2）遍历完整链表，后一个节点的random赋值为前一个节点的random.next
3）遍历链表，拆分
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
if not head:
return head
self.copyNodes(head)
self.connectRandomNodes(head)
return self.reconnectRandomNodes(head)
def copyNodes(self, head):
node = head
while node:
cloned = RandomListNode(0)
cloned.label = node.label
cloned.next = node.next
node.next = cloned
node = cloned.next
def connectRandomNodes(self, head):
node = head
while node:
cloned = node.next
if node.random:
cloned.random = node.random.next
node = cloned.next
def reconnectRandomNodes(self, head):
node = head
clonedHead = clonedNode = node.next
node.next = clonedHead.next
node = node.next
while node:
clonedNode.next = node.next
clonedNode = clonedNode.next
node.next = clonedNode.next
node = node.next
return clonedHead
网友评论