C++实现LeetCode(138.拷贝带有随机指针的链表)

C++实现LeetCode(138.拷贝带有随机指针的链表)攻略

题意描述

给定一个链表，其中每个节点除了next指针外，还有一个random指针，指向链表中的任意节点或者null。请将该链表进行深度拷贝，并返回深度拷贝后的链表。

解题思路

方法一：哈希表

我们可以考虑定义一个哈希表，遍历原链表，建立原节点到新节点的映射关系，并在构建新链表时同时更新random指针的映射关系，最后返回新链表的头节点。具体实现细节请参见下面的代码。

class Solution {
public:
    typedef Node* node_ptr;
    Node* copyRandomList(Node* head) {
        unordered_map<node_ptr, node_ptr> node_map;

        node_ptr itr = head;
        while (itr) {
            node_map[itr] = new Node(itr->val);
            itr = itr->next;
        }

        itr = head;
        while (itr) {
            node_map[itr]->next = node_map[itr->next];
            node_map[itr]->random = node_map[itr->random];
            itr = itr->next;
        }

        return node_map[head];
    }
};

方法二：原地拷贝

另外，在处理该题时还有一种更为巧妙的方法，即原地进行拷贝。具体思想为：在原有链表上，每个节点后面都新增一个相似的节点，且在对这些新增节点进行赋值操作时，可以通过简单的访问即可找到每个新增节点的random指针指向的节点。接下来只需再对原有链表进行遍历，同时更新新链表节点间的指针映射关系，最后返回新链表的头节点即可。具体实现请参考下面代码。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;

        Node* itr = head;
        while (itr) {
            Node* next = itr->next;

            Node* copy = new Node(itr->val);
            itr->next = copy;
            copy->next = next;

            itr = next;
        }

        itr = head;
        while (itr) {
            if (itr->random) itr->next->random = itr->random->next;
            itr = itr->next->next;
        }

        itr = head;
        Node* new_head = head->next;
        while (itr) {
            Node* copy = itr->next;
            itr->next = copy->next;
            if (copy->next) copy->next = copy->next->next;
            itr = itr->next;
        }

        return new_head;
    }
};

示例说明

示例一：

输入：

{7,null}
{13,0}
{11,4}
{10,2}
{1,0}

其中，上面每一行表示一个链表结构，每行两个数字中，第一个数字表示该节点的值，第二个数字表示该节点random指针指向的节点序号，在给定输入中，序号表示该节点在输入中出现的行数（从0开始计算）。

输出：

{7,null}
{13,0}
{11,4}
{10,2}
{1,0}

其中，该输出结果表明，输入数据所表示的链表进行深拷贝后，新的链表与输入链表完全一致。

示例二：

输入：

{1,1}
{2,1}

其中，上面的输入数据表示一个拥有两个节点的链表，其中第一个节点的random指针指向节点1。

输出：

{1,1}
{2,1}

经过深拷贝后，新的链表节点所存储的值和输入数据一致，并且random指针所指向的节点也正确。因此，输出结果与输入数据完全一致。