python - 使用随机指针复制列表。第二个while循环在这里做什么？

Question

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        oldToCopy = { None : None} 
        
        curr = head 
        while curr:
            copy = Node(curr.val)
            oldToCopy[curr] = copy 
            curr = curr.next 
            
        curr = head 
        while curr:
            copy = oldToCopy[curr]
            copy.next = oldToCopy[curr.next]
            copy.random = oldToCopy[curr.random]
            curr = curr.next 
            
        return oldToCopy[head]
            

此代码正在制作链接列表的深层副本。在第一个 while 循环中，我们复制每个节点值并将其放入 hashmap 中。在第二个 while 循环中，我们设置copy为从 hashmap 中获得的值？

copy当我这样做时，从 hashmap中分配copy.next和到值如何返回答案。copy.randomoldToCopy[head]

对这段代码在做什么感到困惑。

标签： pythonpython-3.xlinked-listhashmap

Answer 1

这是一个链表，所以每个节点都有一个指向下一个节点的指针（在这种情况下还有一个指向随机节点的指针）。

第一个循环构造oldToCopy，它是原始节点到节点副本的映射。这意味着当您在其中查找某些内容时，oldToCopy您正在使用原始节点作为键来检索该节点的副本。

然后第二个循环再次遍历原始列表并：

• copy被分配为指向curr在第一个循环中创建的节点的副本（这只是为了方便避免oldToCopy[curr]反复使用）。
• copy.next被赋值为指向所指向的节点的副本curr.next。
• copy.random类似地分配。

为每个副本设置next和random指针是在两个循环中完成的，因为当您复制节点时，x您还没有指向的节点的副本x.next- 您将在下一次迭代中制作该副本。