C语言复杂链表的复制实例详解

一、题目描述

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例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]]

示例4：

输入：head = []

输出：[]解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000

Node.random 为空(null)或指向链表中的节点。

节点数目不超过 1000 。

二、思路分析

注：思路分析中的一些内容和图片参考自力扣各位前辈的题解，感谢他们的无私奉献

分析

复制普通链表：给定链表的头结点head，复制普通链表很简单，只需遍历链表，每轮需要：建立新结点 + 让前驱结点的next指向当前这个新结点 + 让当前这个新结点的next指向空

复制复杂链表：本题链表的结点新增了 random 指针，指向链表中的任意结点或者null。这个 random 指针意味着在复制过程中，除了构建前驱结点的next指针，还要构建前驱结点的ramdom指针。因此，每轮需要：建立2个新结点 + 让前驱结点的next指向第1个新结点 + 让前驱结点的random指向第2个新结点。但是这有一个问题：并不是每次都需要建立2个新结点。有时候前驱结点的random指向的是已经存在的结点，但是如何判断出来呢？如果把所有结点遍历一遍，那就太麻烦了。

思路

利用哈希表的查询特点，考虑构建原链表结点和新链表对应结点的键值对映射关系，再遍历构建新链表各结点的next和random引用指向即可。
 

算法流程：

①若头节点head为空结点，直接返回NULL ；

②初始化：声明一个哈希表dic，定义一个结点cur指向头结点，这个cur控制后面的循环

③建立哈希映射：遍历这个链表，每个链表结点对应建立一个新结点，并向dic添加键值对(原cur结点, 新cur结点)

④构建新链表的引用指向：构建新结点的next和random引用指向

⑤返回值： 返回新链表的头结点，即dic[cur]

三、整体代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        //若是空链表，则返回NULL
        if(head == NULL) return NULL;
        //创建一个结点，指向这个链表的头结点。这个结点用来控制后面的循环
        Node* cur = head; 
        //创建一个哈希表
        unordered_map<Node*, Node*> map;
        while(cur != NULL){
            //为链表每个结点创建一个对应的新结点，并建立原结点和新结点的Map映射
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        //为新链表每个结点的next和random设置对应的指向
        while(cur != NULL){
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        //返回新链表的头结点
        return map[head];
    }
};

总结