【LeetCodeHOT100】 160. 相交链表 —— Java多解法详解

题目链接：160. 相交链表 - 力扣（LeetCode）

一、题目描述

给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。

题目数据保证整个链式结构中不存在环。

注意：函数返回结果后，链表必须保持其原始结构。

【关键理解】：何为相交？
相交指的是节点为同一个节点，即两个指针指向内存中的同一个对象，而不是两个节点值相等。这一点非常重要——不能通过比较val来判断相交，必须用==比较节点引用（即内存地址）。

二、方法概览

注：m和n分别为链表headA和headB的长度。

三、准备工作：链表节点定义

所有解法均基于以下ListNode定义（题目已给出）：

java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */

四、解法一：暴力法（双重循环）

💡 思路

最直接的想法：遍历链表A中的每个节点，对于每个节点，再遍历链表B中的所有节点，看是否有相同的节点（内存地址相同）。第一个找到的相同节点就是交点。

📝 代码实现

java

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode curA = headA; while (curA != null) { ListNode curB = headB; while (curB != null) { if (curA == curB) { return curA; } curB = curB.next; } curA = curA.next; } return null; } }

⏱ 复杂度分析

• 时间复杂度：O(m × n)，最坏情况下需要遍历m × n次。

• 空间复杂度：O(1)，仅使用常数个额外变量。

📌 点评

暴力法是最容易想到的解法，但效率较低。在链表长度较大时（m, n ≤ 3×10⁴）会超时，仅适合理解题意或小规模数据。

五、解法二：哈希表法

💡 思路

利用哈希集合（HashSet）以空间换时间。先用哈希集合存储链表A的所有节点，再遍历链表B，第一个在哈希集合中存在的节点就是交点。由于哈希集合查找是 O(1) 的，整体时间复杂度可以降到 O(m+n)。

📝 代码实现

java

import java.util.HashSet; import java.util.Set; public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } Set<ListNode> visited = new HashSet<>(); // 遍历链表 A，将所有节点加入哈希集合 ListNode curA = headA; while (curA != null) { visited.add(curA); curA = curA.next; } // 遍历链表 B，第一个在集合中的节点就是交点 ListNode curB = headB; while (curB != null) { if (visited.contains(curB)) { return curB; } curB = curB.next; } return null; } }

⏱ 复杂度分析

• 时间复杂度：O(m + n)，需要遍历两个链表各一次。

• 空间复杂度：O(m) 或 O(n)，需要存储其中一个链表的所有节点。

📌 点评

哈希表法代码简洁，思路清晰，是面试中常用的解法。缺点是需要额外的 O(m) 或 O(n) 空间。题目中的进阶要求是 O(1) 空间，所以这并非最优解。

六、解法三：栈解法

💡 思路

利用栈“后进先出”的特性。将两个链表的所有节点分别压入两个栈中，然后同时弹出栈顶元素进行比较。由于相交节点之后的节点全部相同，所以从栈顶开始弹出时，最后一组相等的节点之后的下一个节点（即最后一组相等节点的后一个）就是第一个相交的节点。

示意图：

• 链表 A：a1 → a2 → c1 → c2 → c3

• 链表 B：b1 → b2 → b3 → c1 → c2 → c3

• 压栈后，栈顶都是c3，依次弹出：c3、c2相等，c1相等，弹出a2和b3时不再相等。则最后一组相等节点的后一个节点是c1（即第一个相交节点）。

📝 代码实现

java

import java.util.ArrayDeque; import java.util.Deque; public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } Deque<ListNode> stackA = new ArrayDeque<>(); Deque<ListNode> stackB = new ArrayDeque<>(); // 将链表 A 的所有节点压入栈 A ListNode curA = headA; while (curA != null) { stackA.push(curA); curA = curA.next; } // 将链表 B 的所有节点压入栈 B ListNode curB = headB; while (curB != null) { stackB.push(curB); curB = curB.next; } ListNode intersection = null; // 同时弹出栈顶元素，直到遇到不相等的节点 while (!stackA.isEmpty() && !stackB.isEmpty()) { if (stackA.peek() == stackB.peek()) { intersection = stackA.pop(); stackB.pop(); } else { break; } } return intersection; } }

⏱ 复杂度分析

• 时间复杂度：O(m + n)，需要遍历两个链表各两次（一次入栈，一次出栈）。

• 空间复杂度：O(m + n)，需要两个栈存储两个链表的所有节点。

📌 点评

栈解法利用了相交链表“尾部相同”的特性，思路巧妙。但空间复杂度较高，且代码稍显冗长。在面试中可作为备选方案展示思考的多样性。

七、解法四：长度差双指针法

💡 思路

如果两个链表相交，那么相交节点之后的部分长度是相同的。因此，核心思路是：让两个链表从“距离尾部相同距离”的位置开始同时向前遍历。

具体步骤：

1. 分别计算两个链表的长度lenA和lenB。

2. 计算长度差gap = |lenA - lenB|。

3. 让较长的链表先走gap步，此时两个指针距离尾部的距离相等。

4. 两个指针同步向前移动，第一次相遇的节点就是交点。

📝 代码实现

java

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } // 1. 计算两个链表的长度 ListNode curA = headA; ListNode curB = headB; int lenA = 0, lenB = 0; while (curA != null) { lenA++; curA = curA.next; } while (curB != null) { lenB++; curB = curB.next; } // 2. 重新指向头节点 curA = headA; curB = headB; // 3. 让较长的链表先走差值步 int gap = Math.abs(lenA - lenB); if (lenA > lenB) { while (gap-- > 0) { curA = curA.next; } } else { while (gap-- > 0) { curB = curB.next; } } // 4. 同步向前遍历，寻找交点 while (curA != null && curB != null) { if (curA == curB) { return curA; } curA = curA.next; curB = curB.next; } return null; } }

⏱ 复杂度分析

• 时间复杂度：O(m + n)，需要遍历两个链表各两次。

• 空间复杂度：O(1)，仅使用常数个额外变量。

📌 点评

长度差双指针法满足题目进阶要求的 O(1) 空间，思路清晰易懂。需要两次遍历，代码稍长但逻辑明确，是面试中值得推荐的解法之一。

八、解法五：互换遍历双指针法（最优解）

💡 思路

这是本题最优雅、最巧妙的解法，代码极短且无需额外空间。

核心思想：创建两个指针pA和pB，分别指向headA和headB，然后同时向前移动。当一个指针到达链表末尾时，将其重定向到另一个链表的头节点，继续移动。如果两个链表相交，两个指针最终会在相交节点相遇；如果不相交，它们会同时变为null。

数学原理：

• 设链表 A 的长度为a + c（c为公共部分长度），链表 B 的长度为b + c。

• 指针pA走过的总路程为a + c + b，指针pB走过的总路程为b + c + a。

• 两者相等，因此pA和pB会同时到达交点（如果相交）或同时到达null（如果不相交）。

示意图（链表示例）：

text

链表 A：4 → 1 → 8 → 4 → 5 ↗ 链表 B：5 → 0 → 1 （注：实际相交节点是内存地址相同的节点，此处简化示意） pA 路径：4 → 1 → 8 → 4 → 5 → null → 5 → 0 → 1 → 8（在 8 处与 pB 相遇） pB 路径：5 → 0 → 1 → 8 → 4 → 5 → null → 4 → 1 → 8（在 8 处与 pA 相遇）

📝 代码实现

java

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode pA = headA; ListNode pB = headB; // 当 pA == pB 时退出循环 // 如果相交，pA 和 pB 会在交点相遇 // 如果不相交，pA 和 pB 会同时变为 null while (pA != pB) { pA = (pA == null) ? headB : pA.next; pB = (pB == null) ? headA : pB.next; } return pA; } }

⏱ 复杂度分析

• 时间复杂度：O(m + n)，每个指针最多遍历两个链表各一次。

• 空间复杂度：O(1)，仅使用两个指针变量。

📌 点评

这是本题的最优解，也是面试官最希望看到的答案。代码仅需寥寥数行，同时满足时间复杂度 O(m+n) 和空间复杂度 O(1) 的双重要求。核心在于巧妙利用“路程相等”的数学原理，通过互换遍历消除了长度差的影响。

九、解法对比总结

十、注意事项与常见坑点

1. 比较的是节点引用，而非节点值
   这是本题最容易踩的坑！不能通过比较val来判断相交，因为不同节点可能存储相同的值。必须使用==比较节点对象本身（即内存地址）。

2. 不能修改链表结构
   题目明确要求“函数返回结果后，链表必须保持其原始结构”。这意味着不能修改任何节点的next指针或val值。

3. 空链表处理
   如果任一链表为空，直接返回null。

4. 链表无环
   题目已保证链表结构中不存在环，无需额外处理。

十一、官方题解

• LeetCode 官方题解：160. 相交链表 - 官方题解

• 题目链接：160. 相交链表 - 力扣（LeetCode）