資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中帶隨機指標的列表複製
連結串列是一種線性資料結構，其中每個節點都包含兩個塊，一個塊包含節點的值或資料，另一個塊包含下一個節點的地址。
假設我們有一個連結串列，其中每個節點都包含一個隨機指標，該指標指向列表中的其他節點。任務是構建一個與原始列表相同的列表。從包含一些隨機指標的原始列表複製列表稱為連結串列的“深複製”。
例如
輸入-1
輸出
5-> 2 -> 3 -> 7 ->4 ->
說明：如果我們將新列表附加到給定連結串列中原始節點的值，並將原始連結串列的隨機指標替換為新列表中的下一個節點，那麼它將變成 5-> 2- >3 -> 7-> 4->
解決此問題的方法
我們有一個連結串列，其節點包含其資料和指向其隨機節點地址的指標。為了實現包含資料和隨機指標的連結串列的副本，我們將首先在每個節點之後附加一個具有相同值的新節點。這將在每個節點之後建立一個重複的節點。
初始化後，檢查列表中隨機指標的路徑，並將隨機指標相應地插入新建立的節點中。
現在，分離原始列表中每個節點之後的這些新建立的節點將建立連結串列的深複製。
- 獲取一個包含資料欄位和指向其隨機節點地址的指標的連結串列。
- 函式 copyRandomList(listnode*head) 將原始列表的頭節點作為輸入，並返回列表的深複製。
- 如果頭節點為空，則列表為空，我們也必須返回頭節點。
- 現在，在原始列表的每個節點之後插入一個具有相同值的新節點。
- 然後複製原始列表中的隨機指標並插入新節點，即 newnode->next = curr->randomPointer
- 建立了一個帶有指標和資料的新節點後，我們將分離列表並將其作為輸出返回。
示例
#include <bits/stdc++.h>
using namespace std;
struct listnode {
int data;
listnode * next, * random;
listnode(int d) {
data = d;
next = NULL;
random = NULL;
}
};
void print(listnode * head) {
listnode * curr = head;
while (curr) {
cout << curr -> data << " " << curr -> random -> data << endl;
curr = curr -> next;
}
}
listnode * copyRandomList(listnode * head) {
if (!head) {
return head;
}
//Insert a new node with the same value after each node in the original list.
listnode * curr = head;
while (curr) {
listnode * newHead = new listnode(curr -> data);
newHead -> next = curr -> next;
curr -> next = newHead;
curr = curr -> next -> next;
}
//Now place the randompointer with the newly created node.
curr = head;
while (curr) {
if (curr -> random)
(curr -> next) -> random = (curr -> random) -> next;
curr = curr -> next -> next;
}
//Now Let us separate the newly created list
curr = head;
listnode * result = curr -> next;
listnode * dummyHead = new listnode(-1);
dummyHead -> next = result;
while (curr) {
curr -> next = result -> next;
curr = curr -> next;
if (curr) {
result -> next = curr -> next;
}
result = result -> next;
}
result = dummyHead -> next;
delete dummyHead;
return result;
}
int main() {
listnode * head = new listnode(5);
head -> next = new listnode(6);
head -> next -> next = new listnode(3);
head -> next -> next -> next = new listnode(4);
head -> next -> next -> next -> next = new listnode(2);
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;
cout << "Original list :" << endl;
print(head);
cout << "Deep Copy of the List:" << endl;
listnode * deep_copyList = copyRandomList(head);
print(deep_copyList);
return 0;
}執行以上程式碼將生成以下輸出：
輸出
Original List: 5 3 6 5 3 2 4 2 2 6 Deep Copy of the List: 5 3 6 5 3 2 4 2 2 6
更新於： 2021年2月23日
651 次檢視
廣告