算法1（哈希表）
举例说明：
复杂链表：{1,2,3,4,5,3,5,#,2,#}
（1）初始化哈希表dict，节点cur指向头节点
（2）复制链表；建立新节点，循环遍历链表，并向 dict 添加键值对 (原 cur 节点, 新 cur 节点）
（3）构建新链表的引用指向；cur遍历原链表，构建新节点的next、random引用指向
（4）返回新链表的头节点 dict[pHead]
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if pHead is None:
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] 算法2（链表拼接、拆分）
解题思路
- 此解法参考了大佬的做法, 主要思路是将原链表的结点对应的拷贝节点连在其后, 最后链表变成 原1 -> 拷1 -> 原2 -> 拷2 -> ... -> null 的形式
- 然后我们再逐步处理对应的随机指针, 使用双指针, 一个指针指向原链表的节点, 一个指向拷贝链表的节点, 那么就有 拷->random = 原->random->next (random不为空)
- 最后再用双指针将两条链表拆分即可, 此算法大大优化了空间复杂度, 十分优秀
class Solution: # 返回 RandomListNode def Clone(self, pHead): # write code here if pHead is None: return None dummy = RandomListNode(-1) dummy.next = pHead while pHead!=None: node = RandomListNode(pHead.label) node.next = pHead.next pHead.next = node pHead = node.next pHead = dummy.next while pHead !=None: if pHead.random !=None: pHead.next.random = pHead.random.next pHead = pHead.next.next pHead = dummy.next ans = pHead.next while pHead !=None: tmp = pHead.next if pHead.next !=None: pHead.next = pHead.next.next pHead = tmp return ans
参考资料：
京公网安备 11010502036488号