1. 从一道题看链表算法的核心思维1.1 为什么“相交链表”值得单独拿出来讲LeetCode上标签为“链表”的题目少说也有几十道但“相交链表”这道题的地位很特殊。它不像反转链表那样纯粹考察指针操作也不像环形链表那样只考快慢指针它真正考的是你对链表结构本质的理解——两个链表从某个节点开始共享同一段内存这意味着它们之后的节点地址完全相同。我第一次做这道题的时候脑子里第一反应是“用哈希表存一下不就行了”确实能做出来但面试官如果追问“能不能O(1)空间复杂度解决”很多人就卡住了。这道题之所以经典是因为它有一个非常优雅的双指针解法代码短到只有几行但背后的逻辑链条需要你真正想通才能写对。这道题适合谁看如果你刚开始刷链表专题它能帮你建立“指针走位”的直觉如果你已经刷了几十道题它能帮你重新审视“空间换时间”和“时间换空间”的取舍如果你正在准备面试这道题几乎是链表环节的必考题而且变体很多值得吃透。1.2 题目到底在问什么先把题目说清楚。给定两个单链表的头节点headA和headB判断它们是否相交如果相交就返回相交的起始节点不相交就返回null。这里有一个关键前提相交之后的所有节点完全重合。也就是说不会出现“X”形交叉只会出现“Y”形或者“V”形。这个前提非常重要因为它是所有解法成立的基础。你可以想象两条路从不同方向出发在某一个路口汇合之后就是同一条路了。题目还给了两个额外的约束函数返回结果后链表必须保持原始结构整个链表中不能有环。这两个约束看起来是废话但实际上是在排除一些取巧的做法比如把链表改成环形再判断之类的。我见过不少人在面试时被问到这道题第一反应是“遍历A把节点存到集合里再遍历B看有没有重复”这个思路没问题时间复杂度O(mn)但空间复杂度也是O(mn)。面试官通常会接着问“能不能把空间降到O(1)”这时候就需要双指针出场了。2. 三种解法逐一拆解2.1 最直观的哈希集合法先说说最容易想到的解法。思路很简单遍历链表A把每个节点的引用或者内存地址存到一个哈希集合里然后遍历链表B每遇到一个节点就查一下集合里有没有第一个查到的就是相交起始节点。Java版本的代码大概长这样public ListNode getIntersectionNode(ListNode headA, ListNode headB) { SetListNode visited new HashSet(); ListNode cur headA; while (cur ! null) { visited.add(cur); cur cur.next; } cur headB; while (cur ! null) { if (visited.contains(cur)) { return cur; } cur cur.next; } return null; }Python版本更简洁def getIntersectionNode(self, headA, headB): visited set() cur headA while cur: visited.add(cur) cur cur.next cur headB while cur: if cur in visited: return cur cur cur.next return None这个解法的时间复杂度是O(mn)空间复杂度也是O(mn)。它的优点是逻辑直白不容易写错适合在面试中先快速给出一个可行解。但缺点也很明显如果链表很长哈希集合会占用大量额外内存。注意在Python里set存的是对象的引用对于自定义的ListNode类默认的哈希是基于对象id的所以能正确判断“是不是同一个节点”。但如果你重写了__eq__方法就要小心了可能会出问题。2.2 双指针法优雅的O(1)空间解法双指针法是这道题的精髓。核心思路是两个指针分别从headA和headB出发同步向前走走到null之后就跳到另一个链表的头部继续走。这样如果两个链表相交它们一定会在相交节点相遇如果不相交它们会同时走到null。为什么这样能行我们来算一笔账。假设链表A的独有部分长度为a链表B的独有部分长度为b相交部分长度为c。指针pA走的路径是acb指针pB走的路径是bca。因为acb等于bca所以两个指针走过的总步数相同最终会同时到达相交节点。如果两个链表不相交那么acb和bca都等于mn两个指针会同时走到null循环结束返回null。Java实现public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA null || headB null) return null; ListNode pA headA, pB headB; while (pA ! pB) { pA (pA null) ? headB : pA.next; pB (pB null) ? headA : pB.next; } return pA; }Python实现def getIntersectionNode(self, headA, headB): if not headA or not headB: return None pA, pB headA, headB while pA ! pB: pA pA.next if pA else headB pB pB.next if pB else headA return pA这段代码短到令人发指但第一次看的人往往会懵为什么pA走到null之后要跳到headB为什么这样就能保证相遇我用一个具体的例子来演示。假设链表A是1→2→3→4→5链表B是6→7→4→5相交节点是4。a2节点1、2b2节点6、7c2节点4、5。pA的路径1→2→3→4→5→null→6→7→4 pB的路径6→7→4→5→null→1→2→3→4数一数pA走了8步到达4pB也走了8步到达4。完美相遇。提示这个解法有一个容易写错的地方——判断pA null而不是pA.next null。如果写成pA.next null再跳转逻辑就错了因为你会跳过null这个关键状态。2.3 长度差法先对齐再同步走还有一种思路也很常见先分别遍历两个链表算出长度差d然后让长的那个链表先走d步之后两个指针同步走相遇点就是相交节点。这个思路比双指针法更符合直觉但代码量稍多。Java版本public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA getLength(headA), lenB getLength(headB); ListNode pA headA, pB headB; if (lenA lenB) { for (int i 0; i lenA - lenB; i) pA pA.next; } else { for (int i 0; i lenB - lenA; i) pB pB.next; } while (pA ! pB) { pA pA.next; pB pB.next; } return pA; } private int getLength(ListNode head) { int len 0; while (head ! null) { len; head head.next; } return len; }Python版本def getIntersectionNode(self, headA, headB): lenA, lenB self.getLength(headA), self.getLength(headB) pA, pB headA, headB if lenA lenB: for _ in range(lenA - lenB): pA pA.next else: for _ in range(lenB - lenA): pB pB.next while pA ! pB: pA pA.next pB pB.next return pA def getLength(self, head): length 0 while head: length 1 head head.next return length这个解法的时间复杂度是O(mn)空间复杂度O(1)。它比双指针法多遍历了一遍链表但逻辑更清晰不容易在面试时写错。我个人在面试中更倾向于先写这个版本因为面试官能一眼看懂你的思路沟通成本低。2.4 三种解法的对比与选择解法时间复杂度空间复杂度代码量面试推荐度哈希集合O(mn)O(mn)中等作为保底方案双指针O(mn)O(1)极短强烈推荐长度差O(mn)O(1)中等稳妥选择如果你在面试中时间充裕可以先说哈希集合的思路然后主动提出“可以优化到O(1)空间”再写双指针法。这样既展示了你的思维过程又体现了优化意识。3. 完整实操过程与代码实现3.1 链表节点的定义在开始写解法之前先把链表节点的定义搞清楚。Java中通常是这样public class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } }Python中更简单class ListNode: def __init__(self, x): self.val x self.next None注意LeetCode的Python环境里ListNode的__eq__方法没有被重写所以默认比较的是对象身份。这意味着两个值相同但不同对象的节点不会被判定为相等这正是我们需要的。3.2 本地测试环境的搭建光看代码不够得实际跑一遍才能发现问题。我建议在本地搭一个简单的测试环境手动构造相交链表来验证。Java测试代码public class Main { public static void main(String[] args) { // 构造链表A: 1-2-3-4-5 ListNode common new ListNode(4); common.next new ListNode(5); ListNode headA new ListNode(1); headA.next new ListNode(2); headA.next.next new ListNode(3); headA.next.next.next common; // 构造链表B: 6-7-4-5 ListNode headB new ListNode(6); headB.next new ListNode(7); headB.next.next common; Solution sol new Solution(); ListNode result sol.getIntersectionNode(headA, headB); System.out.println(result ! null ? result.val : null); // 输出应该是4 } }Python测试代码def build_lists(): common ListNode(4) common.next ListNode(5) headA ListNode(1) headA.next ListNode(2) headA.next.next ListNode(3) headA.next.next.next common headB ListNode(6) headB.next ListNode(7) headB.next.next common return headA, headB headA, headB build_lists() sol Solution() result sol.getIntersectionNode(headA, headB) print(result.val if result else null)跑一遍之后你会发现双指针法确实能正确返回节点4。但这里有一个坑如果你不小心把common节点复制了一份而不是共享引用那就不叫相交链表了测试会失败。3.3 边界情况的处理这道题的边界情况不算多但每一个都得考虑到两个链表都为空直接返回null。其中一个为空直接返回null。两个链表不相交双指针法会同时走到null返回null。两个链表在头节点就相交双指针法第一次比较就相等直接返回headA。两个链表长度相差极大比如A有1000个节点B只有1个节点且不相交。双指针法仍然正确只是pB会多跳几次。我在本地测试时专门构造了一个“长度差极大”的用例发现双指针法在极端情况下依然稳定。但要注意如果链表有环这个解法会死循环。题目保证了无环所以没问题。提示如果你在面试中被问到“如果链表可能有环怎么办”可以先判断是否有环如果有环就转换成环形链表相交问题那是另一个话题了。4. 常见问题与排查技巧实录4.1 为什么我的双指针法死循环了这是新手最容易踩的坑。死循环通常有两个原因第一个原因是跳转逻辑写错了。比如写成了pA pA.next null ? headB : pA.next这样当pA走到最后一个节点时pA.next是null直接跳到headB但pA本身没有变成null导致两个指针永远不相等。正确的写法是pA (pA null) ? headB : pA.next先判断当前指针是否为null再决定下一步。第二个原因是两个链表不相交时指针没有同时到达null。如果你在跳转时没有正确处理null状态两个指针可能会错开导致永远不相遇。4.2 哈希集合法在Python中的陷阱Python的set是基于哈希的对于自定义对象默认使用id()作为哈希值。这通常没问题但如果你在ListNode里定义了__eq__和__hash__就可能出问题。我见过一个案例某同学在ListNode里加了__eq__方法比较val值结果哈希集合把两个值相同但不同对象的节点判定为相等导致返回了错误的相交节点。所以除非你明确知道自己在做什么否则不要随便重写ListNode的__eq__。4.3 长度差法的边界计算长度差法有一个容易忽略的边界当两个链表长度相等时d0不需要提前走。这时候两个指针同步走逻辑是正确的。但如果两个链表不相交且长度相等两个指针会同时走到nullwhile循环条件pA ! pB在第一次判断时就是false因为都是null直接返回null。这也是正确的。注意在长度差法中计算长度时需要遍历整个链表这会改变链表的结构吗不会只是读取而已。但如果你在遍历时不小心修改了next指针那就麻烦了。4.4 常见问题速查表问题现象可能原因解决方法死循环跳转逻辑写错用pA null判断不要用pA.next null返回错误节点哈希集合重写了__eq__不要重写ListNode的__eq__空指针异常没有判空开头加if (headA null不相交时返回错误跳转次数不对确保两个指针走过相同总步数Python中set判断失效对象可变确保ListNode不可变或使用id()4.5 面试中的追问与应对面试官在看完你的双指针解法后可能会追问几个问题“如果两个链表不相交你的代码会怎样”——两个指针会同时走到null循环结束返回null。“你能证明两个指针一定相遇吗”——可以设A独有部分长aB独有部分长b公共部分长c。pA走acbpB走bca两者相等所以相遇。“如果链表有环呢”——这个解法不适用需要先判断环再转换成环形链表相交问题。“能不能不用额外变量”——双指针法已经只用了两个指针变量空间复杂度O(1)。5. 从这道题延伸出的链表思维5.1 快慢指针的通用套路相交链表这道题虽然用的是“同步指针”而不是“快慢指针”但它背后的思想是相通的通过控制指针的走位来对齐信息。快慢指针在环形链表、找中点、找倒数第k个节点等题目中都有应用核心都是让两个指针以不同速度或不同起点出发在某个特定时刻相遇。我建议把这几道题放在一起刷环形链表、环形链表II、相交链表、删除链表的倒数第N个节点。刷完之后你会发现链表题的核心就是“指针怎么走”想清楚走位代码自然就出来了。5.2 空间换时间的取舍哈希集合法和双指针法代表了两种典型的算法思维前者用额外空间换取逻辑简单后者用逻辑复杂度换取空间效率。在实际工程中这两种取舍无处不在。比如在数据库查询中建索引就是用空间换时间在缓存设计中用内存换响应速度。理解这种取舍比单纯记住一道题的解法更重要。5.3 链表题在面试中的定位链表题在面试中通常不会太难但很能考察基本功。面试官通过链表题看你是否具备以下能力能否正确处理指针操作不写出空指针异常能否分析时间和空间复杂度能否在给出可行解后主动优化能否清晰解释自己的思路相交链表这道题几乎覆盖了以上所有点所以出现频率极高。我个人的经验是把这道题练到“闭着眼睛都能写对”的程度面试时遇到链表题心里就有底了。5.4 一个容易被忽略的细节最后分享一个我在实际编码中发现的细节在Java中比较两个ListNode是否相等用的是而不是.equals()。因为ListNode没有重写equals方法比较的是对象引用这正是我们需要的。如果你不小心用了.equals()而ListNode又继承了Object的默认实现那结果和一样但代码可读性会让人困惑。在Python中比较用is还是对于ListNodeis比较的是对象身份默认也是比较对象身份因为没有重写__eq__。但为了明确表达“判断是不是同一个节点”的意图我建议用is。这样读代码的人一眼就知道你在比较引用而不是值。提示在团队协作中代码的可读性往往比微小的性能优化更重要。双指针法虽然短但如果你在注释里写清楚“pA走完A走BpB走完B走A总步数相同所以相遇”别人维护起来会轻松很多。这篇文章从一道具体的LeetCode题目出发把三种解法、实操细节、常见坑点和延伸思维都梳理了一遍。如果你正在刷链表专题建议把这道题多写几遍直到能不看题解直接写出双指针版本。链表题就是这样想清楚了就很简单想不清楚就处处是坑。多练几道手感自然就来了。