复杂链表的复制（Python and C++版本）
2021-04-22 00:26
标签：方法 auto 函数 拷贝 连接 new span load null 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。 来源：力扣（LeetCode） 该链表的特点和有向图的特点一样，故可以转化为图使用BFS或者DFS实现。 如果使用迭代的方法，需要先把每个节点复制一次，然后依次加next关系和random关系。 为了存储节点的关系，使用哈希表存储。 复杂链表的复制（Python and C++版本） 标签：方法 auto 函数 拷贝 连接 new span load null 原文地址：https://www.cnblogs.com/kongzimengzixiaozhuzi/p/13279874.html题目：
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof思路：
Python解法：
1 class Node:
2 def __init__(self, x: int, next: ‘Node‘ = None, random: ‘Node‘ = None):
3 self.val = int(x)
4 self.next = next
5 self.random = random
6
7 class Solution:
8 def copyRandomList(self, head: ‘Node‘) -> ‘Node‘:
9 if head == None: return head
10 # 哈希表存储原节点与对应节点的关系,python哈希表不含默认值，所以尾结点为空的关系要加入!!!!!!!!!!!!!!!!!!!!!
11 mp = {None:None}
12 copyNode = head
13 while copyNode: # 把链表节点复制一份
14 mp[copyNode] = Node(copyNode.val)
15 copyNode = copyNode.next
16
17 copyNode = head # 回到起点
18 while copyNode:
19 mp[copyNode].next = mp[copyNode.next] # 连接拷贝节点的next
20 mp[copyNode].random = mp[copyNode.random] # 连接拷贝节点的rangdom
21 copyNode = copyNode.next
22
23 return mp[head]
C++解法：
1 class Node {
2 public:
3 int val;
4 Node* next;
5 Node* random;
6
7 Node(int _val) {
8 val = _val;
9 next = NULL;
10 random = NULL;
11 }
12 };
13
14 class Solution {
15 public:
16 Node* copyRandomList(Node* head) {
17 if (head == NULL) return head;
18 // unordered_map的底层是哈希表，默认值为空，所以节点为空的情况不需要单独存储！！！！！！！！！！！！！！！！
19 unordered_map
上一篇：剑指offer——数组的逆序对
下一篇：js 字符串或者数组前置补零