题目描述
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
示例
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]
输入:head = []
输出:[]
解释:给定的链表为空(空指针),因此返回 null。
解题思路
1.哈希表法
- 先构建next的部分,构建出新的链表。同时将原来的链表和新链表的关系保存在哈希表中,具体为
dict[predNode] = currentNode
- 构建random部分,根据哈希表,
currentNode = dict[predNode]
,currentNode.random = dict[predNode].random = dict[predNode.random]
- 该方法空间复杂度为 O ( n ) O(n) O(n),时间复杂度也为 O ( n ) O(n) O(n)
class Solution(object):
def copyRandomList(self, head):
"""
:type head: Node
:rtype: Node
"""
nodeDict = {}
if not head: return head
elif not head.next:
newhead = Node(head.val)
if not head.random:
return newhead
else:
newhead.random = newhead
return newhead
else:
p1 = head
headNode = Node(head.val)
ph = newhead = headNode
nodeDict[head] = ph
p1 = p1.next
while p1:
newNode = Node(p1.val)
ph.next = newNode
ph = ph.next
nodeDict[p1] = ph
p1 = p1.next
ph.next = None
ph = headNode
while ph:
if head.random:
nodeDict[head].random = nodeDict[head.random]
else:
ph.random = None
head = head.next
ph = ph.next
return newhead