使用随机指针复制列表。第二个 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 循环中，我们复制每个节点值并将其放入哈希图中。在第二个 while 循环中，我们将 copy 设置为从 hashmap?

中获取的值

当我执行 oldToCopy[head].[=16= 时，将 copy、copy.next 和 copy.random 分配给散列图 return 中的值如何得到答案]

对这段代码的作用感到困惑。

Answer 1

它是一个链表，所以每个节点都有一个指向下一个节点的指针（在本例中还有一个指向随机节点的指针）。

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

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

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

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

Answer 2

第一个循环只是使用现有节点的值创建新节点。（此处未分配引用。）

说一个节点 - node1 有 val=5, next=node2 和 random=node4

oldToCopy = {node1: new_node1}

第二个循环将引用（next 和 random）分配给新创建的节点。

从node1开始，next=node2和random=node4，新创建的new_node1也应该有相同的引用但它们必须指向新创建的节点 - new_node2 和 new_node4。而不是旧的（node2 和 node4）。

这就是这段代码对每个新创建的节点所做的。

# Gets the new node/copy of curr node from dict
copy = oldToCopy[curr]
# set the next pointer 
copy.next = oldToCopy[curr.next]
# set the random pointer
copy.random = oldToCopy[curr.random]
# move to the next node
curr = curr.next

Answer 3

通过示例可能有助于形象化该过程：

 head          ┌──────────────────────┐
  ↓            │                      v
┌─────────────┐│  ┌─────────────┐   ┌─────────────┐
│ val: 1      ││  │ val: 2      │   │ val: 3      │
│ next: ───────│─>│ next: ─────────>│ next:None   │
│ random: ─────┘  │ random: None│<─────── :random │
└─────────────┘   └─────────────┘   └─────────────┘

所以这个例子是一个有3个节点的链表。第一个具有对最后一个节点的 random 引用。最后一个节点有一个 random 对中间节点的引用。中间节点没有random引用（是None）。

这是第一个循环完成后的结果：

 head          ┌──────────────────────┐
  ↓            │                      v
┌─────────────┐│  ┌─────────────┐   ┌─────────────┐
│ val: 1      ││  │ val: 2      │   │ val: 3      │
│ next: ───────│─>│ next: ─────────>│ next: None  │
│ random: ─────┘  │ random: None│<─────── :random │
└─────────────┘   └─────────────┘   └─────────────┘
   oldToCopy         oldToCopy         oldToCopy
       │                 │                 │
       │                 │                 │
       v                 v                 v
┌─────────────┐   ┌─────────────┐   ┌─────────────┐
│ val: 1      │   │ val: 2      │   │ val: 3      │
│ next: None  │   │ next: None  │   │ next: None  │
│ random: None│   │ random: None│   │ random: None│
└─────────────┘   └─────────────┘   └─────────────┘

上图的一些解释现在有很多参考：

下面三个节点是用new Node()创建的新节点。
那些新节点中的引用（即它们的 next 和 random 属性）都是 None，因为我们没有（也不能）通过任何好的这些属性的值。新节点仅正确设置了 val 属性。
oldToCopy 是由旧节点键入的字典。给定一个旧节点，它给出对应的新节点。所以这也用向下的箭头表示。

现在让我们逐步完成第二个循环。

首先curr和copy定义如下：

 curr
 head          ┌──────────────────────┐
  ↓            │                      v
┌─────────────┐│  ┌─────────────┐   ┌─────────────┐
│ val: 1      ││  │ val: 2      │   │ val: 3      │
│ next: ───────│─>│ next: ─────────>│ next: None  │
│ random: ─────┘  │ random: None│<─────── :random │
└─────────────┘   └─────────────┘   └─────────────┘
   oldToCopy         oldToCopy         oldToCopy
       │                 │                 │
       │                 │                 │
       v                 v                 v
┌─────────────┐   ┌─────────────┐   ┌─────────────┐
│ val: 1      │   │ val: 2      │   │ val: 3      │
│ next: None  │   │ next: None  │   │ next: None  │
│ random: None│   │ random: None│   │ random: None│
└─────────────┘   └─────────────┘   └─────────────┘
  ↑
 copy

然后我们执行copy.next = oldToCopy[curr.next]。我们注意到 curr.next 是中间的旧节点。 oldToCopy[curr.next] 是它正下方的节点（新节点）。因此 copy.next = oldToCopy[curr.next] 对第一个新节点的 next 属性有这样的影响：

 curr
 head          ┌──────────────────────┐
  ↓            │                      v
┌─────────────┐│  ┌─────────────┐   ┌─────────────┐
│ val: 1      ││  │ val: 2      │   │ val: 3      │
│ next: ───────│─>│ next: ─────────>│ next: None  │
│ random: ─────┘  │ random: None│<─────── :random │
└─────────────┘   └─────────────┘   └─────────────┘
   oldToCopy         oldToCopy         oldToCopy
       │                 │                 │
       │                 │                 │
       v                 v                 v
┌─────────────┐   ┌─────────────┐   ┌─────────────┐
│ val: 1      │   │ val: 2      │   │ val: 3      │
│ next: ─────────>│ next: None  │   │ next: None  │
│ random: None│   │ random: None│   │ random: None│
└─────────────┘   └─────────────┘   └─────────────┘
  ↑
 copy

当我们执行 copy.random = oldToCopy[curr.random] 时会发生类似的事情。 curr.random 是最后一个旧节点。 oldToCopy[curr.random] 是它正下方的节点。因此 copy.random = oldToCopy[curr.random] 对第一个新节点的 random 属性有这样的影响：

 curr
 head          ┌──────────────────────┐
  ↓            │                      v
┌─────────────┐│  ┌─────────────┐   ┌─────────────┐
│ val: 1      ││  │ val: 2      │   │ val: 3      │
│ next: ───────│─>│ next: ─────────>│ next: None  │
│ random: ─────┘  │ random: None│<─────── :random │
└─────────────┘   └─────────────┘   └─────────────┘
   oldToCopy         oldToCopy         oldToCopy
       │                 │                 │
       │                 │                 │
       v                 v                 v
┌─────────────┐   ┌─────────────┐   ┌─────────────┐
│ val: 1      │   │ val: 2      │   │ val: 3      │
│ next: ─────────>│ next: None  │   │ next: None  │
│ random: ───────┐│ random: None│   │ random: None│
└─────────────┘  │└─────────────┘   └─────────────┘
  ↑              │                   ^
 copy            └───────────────────┘

循环的第一次迭代通过将 curr 引用移动到原始列表中的下一个节点来完成。此迭代使第一个新节点的 next 和 random 属性引用新节点而不是旧节点。

下一次迭代将对第二个新节点执行相同的操作——其中 random 曾经是并且仍然是 None，但是 next 将被重新连接——所以我们得到：

               ┌──────────────────────┐
 head          │   curr               │
  ↓            │    ↓                 v
┌─────────────┐│  ┌─────────────┐   ┌─────────────┐
│ val: 1      ││  │ val: 2      │   │ val: 3      │
│ next: ───────│─>│ next: ─────────>│ next: None  │
│ random: ─────┘  │ random: None│<─────── :random │
└─────────────┘   └─────────────┘   └─────────────┘
   oldToCopy         oldToCopy         oldToCopy
       │                 │                 │
       │                 │                 │
       v                 v                 v
┌─────────────┐   ┌─────────────┐   ┌─────────────┐
│ val: 1      │   │ val: 2      │   │ val: 3      │
│ next: ────────> │ next: ─────────>│ next: None  │
│ random: ───────┐│ random: None│   │ random: None│
└─────────────┘  │└─────────────┘   └─────────────┘
                 │  ↑                 ^
                 │ copy               │
                 └────────────────────┘

最后一次迭代将对最后一个新节点执行相同操作：

 head          ┌──────────────────────┐  curr
  ↓            │                      v   ↓
┌─────────────┐│  ┌─────────────┐   ┌─────────────┐
│ val: 1      ││  │ val: 2      │   │ val: 3      │
│ next: ───────│─>│ next: ─────────>│ next: None  │
│ random: ─────┘  │ random: None│<─────── :random │
└─────────────┘   └─────────────┘   └─────────────┘
   oldToCopy         oldToCopy         oldToCopy
       │                 │                 │
       │                 │                 │
       v                 v                 v
┌─────────────┐   ┌─────────────┐   ┌─────────────┐
│ val: 1      │   │ val: 2      │   │ val: 3      │
│ next: ────────> │ next: ─────────>│ next: None  │
│ random: ───────┐│ random: None│<─────── :random │
└─────────────┘  │└─────────────┘   └─────────────┘
                 │                    ^    ↑
                 └────────────────────┘   copy

最后，函数returns oldToCopy[head]，它是对克隆列表的引用，现在不再引用旧节点。

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

Copy List with Random Pointer. What is the second while loop doing here?

python

linked-list

hashmap

python-3.x