日野弥生：勉強しよう
LeetCode 138 - 随机链表的复制
发表于2025年02月05日
先遍历第一次原链表，按顺序构建新链表节点和next成员变量。再遍历一次构建random成员。 此处可以考虑创建两个辅助字典进行快速查找，旧链表构建的字典key和value分别是链表节点对应到索引，新链表构建的字典key和value分别是索引对应到新链表结点。
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
# 判空，注意对象判空最好使用is和is not，而不是==和!=
if head is None:
return None
oldDict, newDict = dict(), dict()
curr = head
index = 0
# 先插入头结点进入两个字典中
oldDict[curr] = index
newHead = Node(curr.val)
newDict[index] = newHead
newCurr = newHead
# 判空建议使用is not
while curr.next is not None:
# 循环体插入next结点，可以保证插入结点时前后next成员可以连接
index += 1
oldDict[curr.next] = index
# 创建对象直接调用构造，不需要像C++那样new运算
newCurrNext = Node(curr.next.val)
newDict[index] = newCurrNext
newCurr.next = newCurrNext
# 遍历
newCurr = newCurrNext
curr = curr.next
# 第二次循环填充random成员
curr = head
newCurr = newHead
while curr is not None:
# 判空直接写入空
if curr.random is None:
newCurr.random = None
else:
# 通过两本字典可以迅速查找出radom指向的对象
newCurr.random = newDict.get(oldDict.get(curr.random))
newCurr = newCurr.next
curr = curr.next
return newHead