Problem: 160. 相交链表

思路

参考：

• 哈希表：https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/811625/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/?envType=study-plan-v2&envId=top-100-liked

• 双指针：https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/12624/intersection-of-two-linked-lists-shuang-zhi-zhen-l/?envType=study-plan-v2&envId=top-100-liked

解题方法

哈希表

1. python中链表的处理，常常可以将链表复制进入哈希表实现的数据结构中，如dict或set；

2. 使用什么样的哈希表应该根据实际需求，dict自带索引，set可实现去重；

3. 这里使用set即可，因为不需要返回索引，重点在于检查元素存在与否，且这里的set应该存链表中的node，而非node对应的value，因为value是可以重复的，而set不会存重复元素。

双指针

直接参考K神的思路吧，人和人的脑子确实存在差距。

额外讨论（GPT）

此题目中set存储node而非value

In the context of finding the intersection of two linked lists, what matters is not the value of the nodes, but the nodes themselves – their identity in memory.

In Python, when you add objects (like nodes of a linked list) to a set, the set does not compare the values within the objects, but rather their identities (memory addresses). Even if two nodes have the same value, they are considered distinct if they are different objects (i.e., they reside at different memory addresses).

So, using a set in this scenario is appropriate and effective. It stores references to the nodes themselves, not their values. Therefore, even if the linked list has duplicate values, the set will correctly identify unique nodes based on their memory addresses, allowing the algorithm to find the intersection point correctly.

Code：哈希表

# 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) -> ListNode:

        # 创建一个散列表，用以记录遍历经过的节点
        visited = set()
        
        # 遍历第一个list，并将所有node放入set
        temp = headA
        while temp:
            visited.add(temp)
            temp = temp.next

        # 遍历第二个list，并检查是否有任何node在set中
        temp = headB
        while temp:
            if temp in visited:
                # 发现交叉，返回交叉
                return temp
            temp = temp.next

        # 没有发现交叉
        return None