LeetCode160相交链表Python代码map[headB]==1运行报错原因咨询

问题描述 #

题目要求：给定两个单链表的头节点headA和headB，返回两个链表相交的起始节点。
编写哈希表法解题时出现如下现象：

• 先通过字典存储遍历过的链表A所有节点
• 后续遍历链表B时，使用if map[headB]==1判断节点是否存在会触发运行时错误
• 改用if headB in map的判断写法可正常运行

对应问题代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        
        map=dict()
        
        while (headA):
            map[headA]=1
            headA=headA.next
        
        while (headB):
            if map[headB]==1: # 这里为什么无法正常运行？换成'if headB in map'就可以
                return headB
            headB=headB.next
        
        return None

报错根因 #

两种写法的底层逻辑完全不同：

• 写map[headB]时，是直接从字典中取key为headB对应的值。Python字典的方括号取值逻辑有明确规则：如果传入的key不存在于字典中，会直接抛出KeyError运行时异常。遍历链表B时，大部分非相交节点只属于链表B、没有被存入字典，取这些节点对应的值时会直接触发KeyError，代码还没执行到==1的比较步骤就已经崩溃。
• 写headB in map时，执行的是字典的成员存在性判断，只会检查key是否在字典的键集合中，存在返回True、不存在返回False，不会触发取值操作，因此不会抛出KeyError，可以正常运行。

补充提示：不建议使用map作为变量名，map是Python内置的高阶函数，用它做变量名会覆盖内置函数实现，可能引发其他隐性问题，可替换为visited这类语义清晰、无命名冲突的变量名。

内容的提问来源于stack exchange，提问作者Seungmin Lee