leetcode138.随机链表的复制

题目链接

leetcode

题目描述

给你一个长度为 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 作为传入参数。

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// 链表结点的定义
struct Node {
    int val;
    Node* next;
    Node* random;
    Node(int x) : val(x), next(nullptr), random(nullptr) {}
};

// 辅助函数：创建随机链表
Node* createList(const vector<pair<int, int>>& values) {
    if (values.empty()) {
        return nullptr;
    }

    int n = values.size();
    vector<Node*> nodes(n);

    for (int i = 0; i < n; i++) {
        nodes[i] = new Node(values[i].first);
    }

    for (int i = 0; i < n; i++) {
        if (i+1 < n) {
            nodes[i]->next = nodes[i+1];
        }
        if (values[i].second != -1) {
            nodes[i]->random = nodes[values[i].second];
        }
    }

    return nodes[0];
}

// 辅助函数：打印随机链表
void printList(Node* head) {
    cout << "[";
    Node* cur = head;

    while (cur != nullptr) {
        cout << "[" << cur->val << ",";
        if (cur->random != nullptr) {
            cout << cur->random->val;
        } else {
            cout << "null";
        }
        cout << "]";
        if (cur->next != nullptr) {
            cout << ",";
        }
        cur = cur->next;
    }
    cout << "]" << endl;
}

// 辅助函数：释放链表内存
void deleteList(Node* head) {
    while (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    回溯 + 哈希表

    哈希表优化：
        使用一个哈希表来存储原始结点和其复制结点之间的映射关系。
        在复制过程中，如果已经复制过某个结点，则直接从哈希表中获取其复制结点。
    复制链表：
        对于链表中的每个结点，先检查哈希表中是否已经存在该结点的复制结点。
        如果不存在，则创建新的复制结点，并将其添加到哈希表中。
        然后，复制该结点的 next 和 random 指针。
    递归复制：
        对于 next 和 random 指针指向的结点，递归调用 copyRandomList 函数进行复制。

    时间复杂度：O(n)
        其中 n 是链表的长度。对于每个结点，
        至多访问其「后继结点」和「随机指针指向的结点」各一次，均摊每个点至多被访问两次。
    空间复杂度：O(n)
        哈希表的空间开销。
*/
class Solution_0 {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }

        if (!cachedNode.count(head)) {
            Node* newHead = new Node(head->val);
            cachedNode[head] = newHead;
            newHead->next = copyRandomList(head->next);
            newHead->random = copyRandomList(head->random);
        }

        return cachedNode[head];
    }

private:
    unordered_map<Node*, Node*> cachedNode;
};

/*    
    迭代 + 结点拆分
    每个结点后面复制一个结点，然后再分离出来。
    
    时间复杂度：O(n)
        其中 n 是链表的长度，需要遍历该链表三次。
    空间复杂度：O(1)
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }

        // 复制原链表中的各个结点，构建新的链表
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* newNode = new Node(node->val);
            newNode->next = node->next;
            node->next = newNode;
        }

        // 修改新链表中各个结点的 random 指向
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* newNode = node->next;
            newNode->random = (node->random != nullptr) ? node->random->next : nullptr;
        }

        // 拆分出原链表、新链表
        Node* newHead = head->next;
        for (Node* node = head; node != nullptr; node = node->next) {
            Node* newNode = node->next;
            node->next = node->next->next;
            newNode->next = (newNode->next != nullptr) ? newNode->next->next : nullptr;
        }

        return newHead;
    }
};

// 辅助函数：打印二维数组
void printArray(const vector<pair<int, int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); ++i) {
        cout << "[" << nums[i].first << ",";
        if (nums[i].second == -1) {
            cout << "null";
        } else {
            cout << nums[i].second;
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<vector<pair<int, int>>> head_cases = {
        {{7,-1}, {13,0}, {11,1}, {10,2}, {1,0}},
        {{1,1}, {2,1}},
        {{3,-1}, {3,0}, {3,-1}}
    };
    
    for (size_t i = 0; i < head_cases.size(); i++) {
        auto& nums = head_cases[i];
        cout << "Input: head = ";
        printArray(nums);

        // 创建随机链表
        Node* head = createList(nums);
        cout << "Original List: ";
        printList(head);
        // 复制随机链表
        Node* copy = solution.copyRandomList(head);
        cout << "Copied List: ";
        printList(copy);

        // 释放内存
        deleteList(copy);
        deleteList(head);
    }

    return 0;
}