带有随机指针的复制列表.第二个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,copy.next和copy.random值从哈希图返回一个答案，当我做oldToCopy[head]。

不知道这段代码在做什么

Answer 1

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

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

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

• copy被指定指向在第一个循环中创建的节点curr的副本(这只是为了避免反复使用oldToCopy[curr])。
• copy.next被指定指向curr.next所指向的节点的副本。
• copy.random同样分配。

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

Answer 2

用一个例子可能有助于可视化这个过程:

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

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

Answer 3

First Loop只是创建新的节点使用现有节点的值。(此处没有指定引用。)

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

oldToCopy = {node1: new_node1}

Second Loop将引用(next和random)分配给新创建的节点。

由于node1s, 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