亲宝软件园·资讯

展开

C语言复杂链表的复制

爱你哦小猪猪 人气:0

一、题目描述

请实现 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结点)

④构建新链表的引用指向:构建新结点的nextrandom引用指向

⑤返回值: 返回新链表的头结点,即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];
    }
};

在这里插入图片描述

总结

本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注的更多内容!     

加载全部内容

相关教程
猜你喜欢
用户评论