LeetCode 算法：随机链表的复制 c++

原题链接🔗：随机链表的复制
复杂度：中等⭐️⭐️

题目

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和random指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和Y两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个[val, random_index]表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
  你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

• 0 <= n <= 1000
• -10⁴ <= Node.val <= 10⁴
• Node.random 为 null 或指向链表中的节点。

题解

1. 解题思路：

LeetCode 上的 “复制带随机指针的链表” 问题是一个经典的链表问题，它要求你复制一个含有随机指针的链表。这个问题的关键在于如何高效地复制链表，同时保持随机指针的正确性。

• 遍历链表：首先遍历原链表，将每个节点复制一份，并将复制的节点插入到原节点的后面。
• 设置随机指针：再次遍历链表，这次是复制后的链表。由于复制后的节点已经插入到原节点后面，可以直接设置 random 指针。
• 分离链表：最后，将复制后的链表从原链表中分离出来，形成两个独立的链表。

2. 复杂度：时间复杂度O(n)，空间复杂度O(n)。
3. c++ demo：

#include <iostream>
#include <vector>// 定义链表节点
struct Node {int val;int randomIndex;Node* next;Node* random;Node(int val, int randomIndex) : val(val), randomIndex(randomIndex), next(NULL), random(NULL) {}
};class Solution {
public:Node* copyRandomList(Node* head) {if (!head) return NULL;// 遍历链表，复制节点并插入到原节点旁边Node* curr = head;while (curr) {Node* copy = new Node(curr->val, curr->randomIndex); // 创建新节点copy->next = curr->next; // 将新节点的next指向原节点的nextcurr->next = copy; // 将原节点的next指向新节点curr = copy->next;}// 再次遍历链表，设置复制节点的random指针curr = head;while (curr) {if (curr->random != NULL) {curr->next->random = curr->random->next; // 复制random指针}curr = curr->next->next; // 移动到下一个原节点}// 分离原链表和复制的链表Node* dummy = new Node(0, -1); // 创建哑节点，方便分离链表Node* copyCurr = dummy;curr = head;while (curr) {copyCurr->next = curr->next; // 将哑节点的next指向复制节点copyCurr = copyCurr->next;curr->next = curr->next->next; // 将原节点的next指向原节点的下一个原节点curr = curr->next;}Node* copyHead = dummy->next; // 获取复制链表的头节点delete dummy; // 删除哑节点return copyHead;}
};int main() {// 示例：创建一个链表 1 -> 2 -> 3，其中 1 的 random 指向 2，2 的 random 指向 3，3 的 random 为 nullNode* head = new Node(1, 1);Node* node2 = new Node(2, 3);Node* node3 = new Node(3, -1);head->next = node2;node2->next = node3;head->random = node2;node2->random = node3;Solution solution;Node* copiedHead = solution.copyRandomList(head);// 打印复制后的链表Node* curr = copiedHead;while (curr) {std::cout << "Value: " << curr->val << ", Random Index: " << curr->randomIndex << std::endl;curr = curr->next;}// 释放复制链表的内存while (copiedHead) {Node* temp = copiedHead;copiedHead = copiedHead->next;delete temp;}return 0;
}

• 输出结果：

Value: 1, Random Index: 1
Value: 2, Random Index: 3
Value: 3, Random Index: -1