数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python 中带随机指针的列表复制
链接列表是一种线性数据结构，其中每个节点有两个块，一个块包含节点的值或数据，另一个块包含下一个字段的地址。
假设我们有一个链接列表，其中每个节点都包含一个随机指针，该指针指向列表中的其他节点。任务是构建与原始列表相同的列表。从包含一些随机指针的原始列表复制列表称为链接列表的“深拷贝”。
例如
输入-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
# Insert a new node with the same value after each node in the original list.
curr = head
while curr != None:
new = listnode(curr.data)
new.next = curr.next
curr.next = new
curr = curr.next.next
# Now place the randompointer with the newly created node.
curr = head
while curr != None:
curr.next.random = curr.random.next
curr = curr.next.next
# Now Let us separate the newly created list from the original list.
curr = head
temp = head.next
while curr.next != None:
dummyHead = curr.next
curr.next = curr.next.next
curr = dummyHead
return 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.next.random = head.next
print("Original list:\n")
printList(head)
copiedList = copyRandomList(head)
print("\n Deep Copy of the List:")
printList(copiedList)运行以上代码将生成以下输出：
输出
Original list: 1 3 2 1 3 5 4 5 5 2 Deep Copy of the List: 1 3 2 1 3 5 4 5 5 2
更新于： 2021年2月23日
697 次查看
广告