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指向原节点的next
            curr->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 为 null
    Node* 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