使用 Python 中的随机指针复制列表
pythonserver side programmingprogramming更新于 2024/2/18 17:34:00
链表是一种线性数据结构，其中每个节点都有两个块，其中一个块包含节点的值或数据，另一个块包含下一个字段的地址。
假设我们有一个链表，每个节点都包含一个指向列表中其他节点的随机指针。任务是构建与原始列表相同的列表。从具有一些随机指针的原始列表复制列表称为"深度复制"的链表。
例如
输入 1:
输出:
5-> 2 -> 3 -> 7 ->4 ->
解释:
如果我们将给定链表中原始节点的值附加到新列表中，并将原始链表的随机指针替换为新列表中的下一个节点，则它将变成 5-> 2- >3 -> 7-> 4->
解决此问题的方法
我们有一个链表，其节点包含其数据和一个随机指针。为了实现包含数据和随机指针的链表的复制，我们首先将在每个节点后附加具有相同值的新节点。这将在每个节点后创建一个重复节点。
初始化后，检查列表中随机指针的路径，并将随机指针相应地放入新创建的节点中。
现在，将原始列表中的每个节点后的新创建的节点分开，将创建链接列表的深层副本。
- 获取带有数据字段和指向其随机节点地址的指针的链接列表。
- 函数 copyRandomList(listnode*head) 将原始列表的头节点作为输入并返回列表的深层副本。
- 如果头为空，则列表为空，我们也必须返回头。
- 现在在原始列表的每个节点后插入一个具有相同值的新节点。
- 然后从原始列表复制随机指针并插入新节点，即 newnode->next = curr->randomPointer
- 一旦使用指针和数据创建新节点，我们将分离列表并返回列表作为输出。
示例
class listnode:
def __init__(self, data):
self.data = data
self.next = None
self.random = None
def copyRandomList(head):
if head is None:
return head
# 在原始列表中的每个节点后插入一个具有相同值的新节点。
curr = head
while curr != None:
new = listnode(curr.data)
new.next = curr.next
curr.next = new
curr = curr.next.next
# 现在将随机指针与新创建的节点放在一起。
curr = head
while curr != None:
curr.next.random = curr.random.next
curr = curr.next.next
# 现在让我们将新创建的列表与原始列表分开。
curr = head
temp = head.next
while curr.next != None:
dummyHead = curr.next
curr.next = curr.next.next
curr = dummyHead
返回 temp
def printList(head):
curr = head
while curr != None:
print(curr.data, " ", curr.random.data)
curr = curr.next
head = listnode(1)
head.next = listnode(2)
head.next.next = listnode(3)
head.next.next.next = listnode(4)
head.next.next.next.next = listnode(5)
head.random = head.next.next
head.next.random = head
head.next.next.random = head.next.next.next.next
head.next.next.next.random = head.next.next.next.next
head.next.next.next.random = head.next.next.next.next
head.next.next.next.next.random = head.next
print("原始列表:\n")
printList(head)
copiedList = copyRandomList(head)
print("\n 列表的深层复制:")
printList(copiedList)
运行上述代码将生成如下输出，
输出
原始列表: 1 3 2 1 3 5 4 5 5 2 列表的深层复制: 1 3 2 1 3 5 4 5 5 2
