在 Python 中带随机和下一个指针的克隆链表

链表是通过随机指针创建的。给定一个 N x N 的链表，其中每个节点有两个连接，一个指向下一个节点，另一个指向列表中的任意节点。我们必须在 O(N) 时间内复制这个链表。

请注意，“next”指针指向链表中的下一个节点，而“random”指针可能指向链表中的任意节点。

方法 - 1

首先创建一个仅包含“next”指针的单链表，然后将新节点映射到其对应的现有链表节点。您现在可以使用新形成的列表中的任何节点来指向任意节点，通过此映射。

以下是上述思路的算法方法

• 对于每个节点（例如 N1），复制它（例如 N2），然后将其映射到其关联的旧节点（例如 map），这样 map[N1] 就等于 N2。
• 使用仅包含“next”指针的复制节点创建单个链表。
• 对之前的链表迭代重复这些步骤
  • 找到映射到现有节点的复制节点。（例如，如果当前节点是 N1，则 map[N1] 是复制节点。）
  • 使当前节点的 -> random 指针指向该节点的复制节点（例如，map[N1] -> random 指向 map[N1 -> random]）。
• 此方法可以生成所需的链表副本。

代码

输出

The initial linked list is as follows:
2(9) -> 6(2) -> 9(15) -> 13(9) -> 15(6)

2 : 2, 6 : 6, 9 : 9, 13 : 13, 15 : 15

The clone of the linked list is:
2(9) -> 6(2) -> 9(15) -> 13(9) -> 15(6)

时间复杂度：此程序的时间复杂度为 O(N)，其中 N 是链表中的节点数。我们没有使用任何嵌套循环，而是以线性方式遍历链表；因此，时间复杂度也是线性的。

辅助空间：程序的空间复杂度也为 O(N)。由于我们创建了一个新的链表，因此空间复杂度是线性的。

方法 2（优化空间复杂度）

下面是优化程序空间复杂度的方法

我们将创建一个复制节点并将其存储在原始节点与其下一个节点之间。

这意味着对于节点 N，我们将创建一个值与 N 相同的节点并将其存储为 N -> next。该节点将充当复制节点。复制节点的随机指针将指向 N -> random -> next，因为它是 N -> random 的复制品。

以下是上述思路的算法方法

• 我们将创建节点 N1 的副本，并将其存储在原始链表中 N1 和 N2 节点之间。同样，我们将创建节点 N2 的副本，并将其存储在 N2 和 N3 节点之间，依此类推。简单来说，我们将创建节点 N 的副本并将其插入到第 N 个节点之后。
• 现在我们将复制随机链接，如下所示：
  • node -> next -> random = node -> random -> next
• 然后，我们将在单个线性循环中分离原始链表和复制链表。
  • node -> next = node -> next -> next
  • clone -> next = clone -> next -> next

代码

输出

The initial linked list is as follows:
2 ( 9 ) -> 6 (2) -> 9 (15) -> 13 (9) -> 15 (6)
The clone of the linked list is:
2 ( 9 ) -> 6 (2) -> 9 (15) -> 13 (9) -> 15 (6)

时间复杂度：此程序的时间复杂度也为 O(N)。我们以线性方式遍历链表，因此时间复杂度也是线性的。

辅助空间：由于在此方法中我们没有创建任何映射，仅将节点对象存储在原始链表中，因此此方法的空间复杂度是常数。空间复杂度为 O(1)。