Python中链表的复制带随机指针的节点
在Python中，链表的复制带随机指针的节点，可以使用哈希表来辅助实现。
假设我们有一个链表，每个节点都有一个next指针和一个random指针，我们需要复制这个链表并返回复制后的链表头。
算法如下：
1.遍历原链表，将每个节点的值和指针映射到哈希表中。
2.再次遍历原链表，对于每个节点，在哈希表中查找与该节点相同值的复制节点，并将复制节点的next和random指针分别指向相应的节点。
3.返回复制后的链表头。
代码实现如下：
class Node: def __init__(self, x): self.val = x self.next = None self.random = None def copyRandomList(head: 'Node') -> 'Node': if head == None: return None # 哈希表存储原节点和复制节点的映射关系 hashmap = {} # 复制节点不含有具体值 dummy = Node(-1) p = dummy # 第一次遍历：复制节点和原节点的映射 cur = head while cur: new_node = Node(cur.val) hashmap[cur] = new_node p.next = new_node p = p.next cur = cur.next # 第二次遍历：建立next和random指针关系 cur = head new_cur = dummy.next while cur: if cur.next: new_cur.next = hashmap[cur.next] if cur.random: new_cur.random = hashmap[cur.random] cur = cur.next new_cur = new_cur.next return dummy.next
我们可以使用以下代码测试：
# 构造链表
a = Node("p")
b = Node("i")
c = Node("d")
d = Node("a")
e = Node("n")
a.next = b
b.next = c
c.next = d
d.next = e
a.random = e
b.random = c
c.random = c
d.random = None
e.random = b
# 复制链表
new_head = copyRandomList(a)
# 验证
cur1 = a
cur2 = new_head
while cur1:
assert cur2.val == cur1.val
if cur1.random:
assert cur2.random.val == cur1.random.val
else:
assert cur2.random == None
cur1 = cur1.next
cur2 = cur2.next
注：该代码仅适用于Python3。
相关文章