LeetCode 160. 相交链表 - 哈希表与双指针解法

一、题目描述

给定两个单链表 headA 和 headB，找出并返回这两个链表相交的起始节点。如果两个链表没有交点，则返回 null。

链表可能具有 不同的长度，但如果它们相交，会在某个节点之后共享相同的尾部。

---

二、示例讲解

示例一

假设有如下两个链表：

ListA: 4 → 1 ↘ 8 → 4 → 5 ↗ ListB: 5 → 6 → 1 

它们在节点值为 8 的位置相交，输出应为该节点。

---

三、解题思路

• 题目理解：两个单链表可能长度不等，若相交则共享尾部部分，否则返回 null。
• 解法思路：
  • 方法一：哈希表存储节点。
  • 方法二：双指针法。
• 复杂度分析：时间复杂度 O(n+m)，空间复杂度 O(1) 或 O(n)。
• 关键目标：找出第一个相交节点。

---

四、解法一：哈希表法

原理说明

1. 首先遍历链表 A，将所有节点加入哈希表。
2. 然后遍历链表 B，每访问一个节点，检查是否在哈希表中出现过。
3. 若出现，则该节点即为相交起点；若遍历完未出现，则返回 null。

时间与空间复杂度

• 时间复杂度：O(n + m)，其中 n 和 m 分别为两个链表的长度。
• 空间复杂度：O(n)，因为需要使用额外哈希表存储链表 A 的节点。

Java 实现

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited =  <>();
           headA;
         (currA != ) {
            visited.add(currA);
            currA = currA.next;
        }
           headB;
         (currB != ) {
             (visited.contains(currB)) {
                 currB; 
            }
            currB = currB.next;
        }
         ; 
    }
}