题目描述
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
思路
方案1:
- 第一步:遍历老链表,构建正常的链表,用一个map记录p到new_p
- 第二步:新老链表同步next移动,对比记录random指针。
p 1->2->3->4 map | | | | new_p 1->2->3->4
需要借助O(n)的空间,时间复杂度为o(n)
方案2:
不需要借助O(n)的空间,时间复杂度为o(n)
老新链表交叉存储,奇数位置为老链表,偶数位置新链表复制前一个位置。
新链表random即为旧链表random的后一个位置。
p1->p1′->p2->p2′->…->pn->pn’
class RandomListNode:
def __init__(self, x):
self.label = x
self.next = None
self.random = None
# 返回 RandomListNode
def Clone(pHead):
# write code here
if not pHead: return None
p = pHead
new_h = RandomListNode(p.label)
pre_p = new_h
random_map = {pHead: new_h}
p = p.next
while p:
new_p = RandomListNode(p.label)
random_map[p] = new_p
pre_p.next = new_p
pre_p = pre_p.next
p = p.next
p = pHead
new_p = new_h
while p:
random_p = p.random
if random_p:
new_p.random = random_map[random_p]
p = p.next
new_p = new_p.next
return new_h
p = RandomListNode(1)
p.next = RandomListNode(2)
p.next.next = RandomListNode(3)
p.next.next.next = RandomListNode(4)
p.next.next.next.next = RandomListNode(5)
print(Clone(p))