题解 | #复杂链表的复制#
复杂链表的复制
http://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba
解题思路：
1、利用哈希表的查询特点，考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向即可
2、考虑构建 原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼接链表，如此便可在访问原节点的 random 指向节点的同时找到新对应新节点的 random 指向节点。
具体步骤：
复制各节点，构建拼接链表:设原链表为 node1→node2→⋯ ，构建的拼接链表如下所示：
node1→node1_new→node2→node2_new →
构建新链表各节点的 random 指向：当访问原节点 cur 的随机指向节点 cur.random 时，对应新节点 cur.next 的随机指向节点为 cur.random.next 。
拆分原 / 新链表：设置 pre / cur 分别指向原 / 新链表头节点，遍历执行 pre.next = pre.next.next 和 cur.next = cur.next.next 将两链表拆分开。
返回新链表的头节点 res 即可。
举例说明：
具体步骤：
复制各节点，构建拼接链表:设原链表为 node1→node2→⋯ ，构建的拼接链表如下所示：
node1→node1_new→node2→node2_new →
构建新链表各节点的 random 指向：当访问原节点 cur 的随机指向节点 cur.random 时，对应新节点 cur.next 的随机指向节点为 cur.random.next 。
拆分原 / 新链表：设置 pre / cur 分别指向原 / 新链表头节点，遍历执行 pre.next = pre.next.next 和 cur.next = cur.next.next 将两链表拆分开。
返回新链表的头节点 res 即可。
举例说明：
复杂链表：{1,2,3,4,5,3,5,#,2,#}
（1）初始化哈希表dict，节点cur指向头节点
（2）复制链表；建立新节点，循环遍历链表，并向 dict 添加键值对 (原 cur 节点, 新 cur 节点）
（3）构建新链表的引用指向；cur遍历原链表，构建新节点的next、random引用指向
（4）返回新链表的头节点 dict[pHead]
图解：
代码:
Python版本:
# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if not pHead:
return None
# 利用字典保存新旧链表节点的对应关系
dict = {}
cur = pHead
# 建立新的链表节点 字典
while cur:
dict[cur] = RandomListNode(cur.label)
cur = cur.next
# 建立新节点的关联字典
cur = pHead
while cur:
dict[cur].next = dict.get(cur.next)
dict[cur].random = dict.get(cur.random)
cur = cur.next
return dict[pHead] JAVA版本： import java.util.Map;
import java.util.HashMap;
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead){
if(pHead == null) return null;
RandomListNode cur = pHead;
Map<randomlistnode> map = new HashMap<>();
// 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
while(cur != null) {
map.put(cur, new RandomListNode(cur.label));
cur = cur.next;
}
cur = pHead;
// 4. 构建新链表的 next 和 random 指向
while(cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
// 5. 返回新链表的头节点
return map.get(pHead);
}
}</randomlistnode> 复杂度分析：
时间复杂度 O(N)： 两轮遍历链表，使用 O(N) 时间。
空间复杂度 O(N) ： 哈希表 dict 使用线性大小的额外空间
文远知行公司福利 265人发布