資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告