第 35 题：复杂链表的复制
传送门：复杂链表的复刻，牛客网 online judge 地址。
请实现一个函数可以复制一个复杂链表。
在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者 null 。
分析：一些细节要考虑到，特别是空结点的判断，以下两种方法都要遍历链表一遍以上，即遍历链表一遍是不够的。
思路1：有点巧妙，穿针引线，新旧断开。
Python 代码：
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
self.random = None
class Solution(object):
def copyRandomList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return None
# 第 1 步：根据 next 指针复制出一个新旧合一的链表
cur_node = head
while cur_node:
# 先暂存 cur_node 的 next_node 下一次遍历要用
next_node = cur_node.next
new_node = ListNode(cur_node.val)
cur_node.next = new_node
new_node.next = next_node
# 指针遍历到下一个结点
cur_node = next_node
# 第 2 步：根据旧结点 random 指针，给新结点的 random 指针做出正确的指向
cur_node = head
while cur_node:
new_node = cur_node.next
# 同样要先暂存 cur_node.next_node
next_node = new_node.next
# 要记得做非空判断，因为题目中说了 random 有可能为空
new_node.random = cur_node.random.next if cur_node.random else None
cur_node = next_node
# 第 3 步：旧结点和新结点分离（拆分链表）
cur_node = head
res = cur_node.next
while cur_node:
new_node = cur_node.next
# 同样要先暂存下一个结点
next_node = new_node.next
# 恢复原始结点
cur_node.next = new_node.next
# 恢复拷贝结点
# 这里也要同样注意空指针的问题，克隆结点的最后一个结点的下一个结点是 null
new_node.next = next_node.next if next_node else None
cur_node = next_node
return res
Java 代码：
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 curNode = pHead;
// 第 1 步：根据 next 指针复制出一个新旧合一的链表
// 此时，奇数索引（从 1 开始计算）的结点是旧的结点，偶数索引的结点是新的结点
RandomListNode nextNode;
RandomListNode copyNode;
while (curNode != null) {
nextNode = curNode.next;
copyNode = new RandomListNode(curNode.label);
curNode.next = copyNode;
copyNode.next = nextNode;
curNode = nextNode;
}
// 第 2 步：根据旧结点 random 指针，给新结点的 random 指针做出正确的指向
// 指针复位到起始结点
curNode = pHead;
while (curNode != null) {
copyNode = curNode.next;
nextNode = copyNode.next;
// 特别注意
// 特别注意
// 特别注意：有的结点很可能 random 的指向为空（题目中明确说明）
// 所以：只要遇到 next 引用的时候，一定要注意判断是否为空
copyNode.random = curNode.random == null ? null : curNode.random.next;
curNode = nextNode;
}
// 第 3 步：旧结点和新结点分离（拆分链表）
curNode = pHead;
RandomListNode res = pHead.next;
while (curNode != null) {
copyNode = curNode.next;
nextNode = copyNode.next;
// 恢复原始结点
curNode.next = copyNode.next;
// 恢复拷贝结点
// 这里也要同样注意空指针的问题，克隆结点的最后一个结点的下一个结点是 null
copyNode.next = copyNode.next == null ? null : copyNode.next.next;
curNode = nextNode;
}
return res;
}
}
C++ 写法：
《剑指 Offer （第 2 版）》第 35 题：复杂链表的复制
Java 版本里面还有一个网友的写法。
思路2：使用哈希表，复制出随机访问的指针。
Python 代码：
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
self.random = None
class Solution(object):
def copyRandomList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return None
map = dict()
dummy_node = ListNode(-1)
# p 指针用于新链表的 next 指针赋值
p = dummy_node
# 遍历一次链表，做两件事
# 1、复制结点
# 2、只管 next 指针
cur_node = head
while cur_node:
new_node = ListNode(cur_node.val)
# 把新旧结点的对应关系放在一个 map 里
map[cur_node] = new_node
cur_node = cur_node.next
p.next = new_node
p = new_node
# 接下来做随机指针的复制
for old_node, new_node in map.items():
# 要记得判断是否为空，否则 None 不能作为 map key
if old_node.random:
new_node.random = map[old_node.random]
return dummy_node.next
Java 代码：
public class Solution3 {
public RandomListNode Clone(RandomListNode pHead) {
Map<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode curNode = pHead;
// 体会这里设置虚拟头结点的必要性
RandomListNode dummyNode = new RandomListNode(-1);
RandomListNode p = dummyNode;
// 完成复制 next 结点，并且将对应关系放入 Hash 表
while (curNode != null) {
RandomListNode newNode = new RandomListNode(curNode.label);
map.put(curNode, newNode);
curNode = curNode.next;
p.next = newNode;
p = newNode;
}
// 完成复制链表的 random 指针的赋值
Set<Map.Entry<RandomListNode, RandomListNode>> entrySet = map.entrySet();
for (Map.Entry<RandomListNode, RandomListNode> entry : entrySet) {
entry.getValue().random = map.get(entry.getKey().random);
}
return dummyNode.next;
}
}
Java 代码：特别注意：在复制“指针”的时候，对空对象的判定，画图是十分关键的。
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 curNode = pHead;
// 第 1 步：根据 next 指针复制出一个新旧合一的链表
// 此时，奇数索引（从 1 开始计算）的结点是旧的结点，偶数索引的结点是新的结点
RandomListNode nextNode;
RandomListNode copyNode;
while (curNode != null) {
nextNode = curNode.next;
copyNode = new RandomListNode(curNode.label);
curNode.next = copyNode;
copyNode.next = nextNode;
curNode = nextNode;
}
// 第 2 步：根据旧结点 random 指针，给新结点的 random 指针做出正确的指向
// 指针复位到起始结点
curNode = pHead;
while (curNode != null) {
copyNode = curNode.next;
nextNode = copyNode.next;
// 特别注意
// 特别注意
// 特别注意：有的结点很可能 random 的指向为空（题目中明确说明）
// 所以：只要遇到 next 引用的时候，一定要注意判断是否为空
copyNode.random = curNode.random == null ? null : curNode.random.next;
curNode = nextNode;
}
// 第 3 步：旧结点和新结点分离（拆分链表）
curNode = pHead;
RandomListNode res = pHead.next;
while (curNode != null) {
copyNode = curNode.next;
nextNode = copyNode.next;
// 恢复原始结点
curNode.next = copyNode.next;
// 恢复拷贝结点
// 这里也要同样注意空指针的问题，克隆结点的最后一个结点的下一个结点是 null
copyNode.next = copyNode.next == null ? null : copyNode.next.next;
curNode = nextNode;
}
return res;
}
}
Java 代码：
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
/**
* 使用 Hash 表的方式
*
* @author liwei
*/
public class Solution2 {
public RandomListNode Clone(RandomListNode pHead) {
Map<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode curNode = pHead;
// 体会这里设置虚拟头结点的必要性
RandomListNode dummyNode = new RandomListNode(-1);
RandomListNode p = dummyNode;
// 完成复制 next 结点，并且将对应关系放入 Hash 表
while (curNode != null) {
RandomListNode newNode = new RandomListNode(curNode.label);
map.put(curNode, newNode);
curNode = curNode.next;
p.next = newNode;
p = newNode;
}
// 完成复制链表的 random 指针的赋值
Set<Map.Entry<RandomListNode, RandomListNode>> entrySet = map.entrySet();
for (Map.Entry<RandomListNode, RandomListNode> entry : entrySet) {
entry.getValue().random = map.get(entry.getKey().random);
}
return dummyNode.next;
}
}
