C语言复杂链表的复制实例详解
目录
- 一、题目描述
- 示例1:
- 示例2:
- 示例3:
- 示例4:
- 二、思路分析
- 三、整体代码
- 总结
一、题目描述
请实现 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]; } };
总结
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注我们的更多内容!