使用 C++ 克隆具有 next 和 Random 指针的链表

2025年3月17日 | 阅读 3 分钟

在本文中，您将学习如何在 C++ 中克隆带有 next 和 Random 指针的链表。

大小为 N 的链表中的每个节点都有两个连接：一个指向紧随其后的节点，另一个可以指向列表中的任何其他节点。这个链表必须在 O(N) 时间内复制。
请记住，“arbit”指针可能会随机指向链表中的任何节点，而“next”指针指向链表中跟随的节点。
下图显示了一个链表示例

Clone a Linked List with next and Random Pointer in C++

使用额外空间克隆带有 next 和 Random 指针的链表

为了将新节点映射到当前链表中匹配的节点，必须首先创建一个仅由“next”指针组成的单链表。通过此映射，您可以使用新创建列表中的任何节点指向任何其他节点。

要应用上述想法，请执行以下操作

复制每个节点（假设为 X），假设为 Y，然后将每个节点映射到其对应的旧节点（假设为 mp），以便 mp[X] = Y。
对于每个节点，仅使用“next”引用，它会创建一个重复节点的单链表。

对于前面的链表迭代，请再次遵循这些步骤

识别与主节点链接的冗余节点。（例如，如果 X 是当前节点，则 mp[x] 是重复节点。）
将当前->arbit 节点的重复节点的 arbit 指针设置为指向该节点的重复节点（使得 mp[x]->arbit 指向 mp[X->arbit]）。

所需的链表，即一个链表，通过此过程创建。

为了澄清，请参考下图

图解

考虑下面显示的链表

arbit 指针是绿色链接。

制作节点和 next 指针的副本

首先创建一个重复节点的单链表，仅使用 next 指针将新节点映射到旧节点。
这里，映射通过蓝色链接显示。

链接 arbit 指针

如技术中所述，现在遍历旧数组并更改 arbit 指针。 arbit 指针是绿色链接。

在第一个节点

在第二个节点

在第三个节点

在第四个节点

在第五个节点

最终的链表如下图所示

程序

让我们举一个例子来演示如何在 C++ 中克隆带有 next 和 random 指针的链表。

#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node* next;
Node* arbit;
Node(int x)
{
this->val = x;
this->next = NULL;
this->arbit = NULL;
}
};
Node* cloneLinkedList(Node* head)
{
unordered_map<Node*, Node*> mp;
Node *temp, *nhead;
temp = head;
nhead = new Node(temp->val);
mp[temp] = nhead;
while (temp->next != NULL) {
nhead->next = new Node(temp->next->val);
temp = temp->next;
nhead = nhead->next;
mp[temp] = nhead;
}
temp = head;
while (temp != NULL) {
mp[temp]->arbit = mp[temp->arbit];
temp = temp->next;
}
return mp[head];
}
void printList(Node* head)
{
cout << head->val << "("<< head->arbit->val << ")";
head = head->next;
while (head != NULL) {
cout << " -> " << head->val << "("<< head->arbit->val << ")";
head = head->next;
}
cout << endl;
}
int main()
{
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
head->arbit = head->next->next;
head->next->arbit = head;
head->next->next->arbit = head->next->next->next->next;
head->next->next->next->arbit = head->next->next;
head->next->next->next->next->arbit = head->next;
cout << "The original linked list:\n";
printList(head);
Node* sol = cloneLinkedList(head);
cout << "The cloned linked list:\n";
printList(sol);
return 0;
}

输出

下一主题在 C++ 中子字符串中至多一个字符的频率为奇数的计数

使用 C++ 克隆具有 next 和 Random 指针的链表

使用额外空间克隆带有 next 和 Random 指针的链表

图解

制作节点和 next 指针的副本

链接 arbit 指针

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

使用 C++ 克隆具有 next 和 Random 指针的链表

使用额外空间克隆带有 next 和 Random 指针的链表

图解

制作节点和 next 指针的副本

链接 arbit 指针

程序

相关帖子

C++ 程序为从单链表中选择随机节点

C++ Ostream

如何在 C++ 中创建游戏引擎

C++ Setf()

C++ 中输入给定字符串所需的最小按键次数

C++ 程序实现八进制到十进制转换

C++ 快速输入输出

C++ 十进制转二进制程序

C++ 和 JAVA 的异常处理

查找数组中最大值的函数 C++

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题