数据结构
网络
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 次查看
广告