剑指35：复杂链表的复制

传送门

nowcoder
leetcode

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针 random 指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。
注意：输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空。

C++ 代码 - nowcoder

/*
    迭代写法，使用哈希表
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if (pHead == nullptr) return nullptr;

        unordered_map<RandomListNode*, RandomListNode*> hash_map;
        // 复制各个节点，建立映射：原节点 -> 新节点
        // for (auto p = pHead; p != nullptr; p = p->next)
        for (RandomListNode* p = pHead; p != nullptr; p = p->next)
            hash_map[p] = new RandomListNode(p->label);
            
        // 连接新链表的 next, random
        // for (auto p = pHead; p != nullptr; p = p->next) {
        for (RandomListNode* p = pHead; p != nullptr; p = p->next) {
            hash_map[p]->next = hash_map[p->next];
            hash_map[p]->random = hash_map[p->random];
        }

        return hash_map[pHead];
    }
};

/*
    递归写法，使用哈希表
*/
class Solution {
public:
    unordered_map<RandomListNode*, RandomListNode*> unmap;

    RandomListNode* Clone(RandomListNode* pHead) {
        if (pHead == nullptr) return nullptr;

        RandomListNode* newHead = new RandomListNode(pHead->label);
        unmap[pHead] = newHead; // pHead -> newHead 映射关系
        newHead->next = Clone(pHead->next); // 到这一步，所有节点已经全部生成
        newHead->random = nullptr;
        if (pHead->random != nullptr) {
            newHead->random = unmap[pHead->random]; // 这一步，重点
        }

        return newHead;
    }
};

C++ 代码 - leetcode

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) 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;
    }
};

/*
	思路同上，实现拆分为多个函数
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;

        copyNextNode(head);
        copyRandomNode(head);
        return splitList(head);
    }

    // 原始链表中所有节点复制一份
    void copyNextNode(Node* head) {
        Node* node = head;
        while (node) {
            Node* temp = new Node(node->val);
            temp->next = node->next;
            node->next = temp;
            node = temp->next;
        }
    }

    // 原始链表中所有节点 random 指向 S，复制节点的 random 指向 S 下一个节点 S' 
    void copyRandomNode(Node* head) {
        Node *node = head, *copyNode = head->next;
        while (node) {
            if (node->random) {
                copyNode->random = node->random->next;
            }
            node = copyNode->next;
            if (node) {
                copyNode = node->next;
            }
        }
    }

    // 拆成两个链表（奇数位置的节点组成原始链表，偶数位置的节点组成复制的链表）
    Node* splitList(Node* head) {
        Node *node = head, *copyNode = head->next, *copyNodeHead = head->next;
        while (node) {
            node->next = copyNode->next;
            node = node->next;
            if (node) {
                copyNode->next = node->next;
            }
            copyNode = copyNode->next;
        }

        return copyNodeHead;
    }
};