相交链表

本文讲解 LeetCode 160. 相交链表的两种解法：哈希集合法和双指针法，并附有 Python 代码实现。

Leetcode Python 哈希表双指针链表

题目

160. 相交链表 - 力扣（LeetCode）

解法一：哈希集合

思路：首先遍历链表 A，将每个节点（注意是节点本身，而非节点值）存入一个哈希集合。然后遍历链表 B，对于每个节点，检查它是否在集合中。第一个在集合中出现的节点就是相交节点。如果遍历完 B 都没有找到，则说明两条链表不相交。

复杂度分析：

时间复杂度：O(m + n)，其中 m 和 n 分别是链表 A 和 B 的长度。
空间复杂度：O(m)，需要存储链表 A 的所有节点。

代码：

# 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]:
        list_set = set()
        temp = headA
        while(temp):
            list_set.add(temp)
            temp = temp.next
        temp = headB
        while(temp):
            if temp in list_set:
                return temp
            temp = temp.next
        return

解法二：双指针

思路：使用两个指针 pa 和 pb 分别从 headA 和 headB 开始遍历。当 pa 走到链表 A 的末尾时，将其重定向到 headB；当 pb 走到链表 B 的末尾时，将其重定向到 headA。这样，两个指针走过的路径长度相同（m + n），如果链表相交，它们会在相交节点相遇；如果不相交，它们会同时到达末尾（均为 None）。

复杂度分析：

时间复杂度：O(m + n)，每个指针最多遍历两条链表各一次。
空间复杂度：O(1)，只使用了两个指针。

代码：

# 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]:
        pa = headA
        pb = headB
        while(pa or pb):
            if pa == pb:
                return pa
            if not pa:
                pa = headB
            else:
                pa = pa.next
            if not pb:
                pb = headA
            else:
                pb = pb.next
        return

总结：双指针法在空间上更优，是面试中推荐的做法。哈希集合法更直观，适合快速理解。