判断两个链表是否相交，核心是检测节点内存地址是否相同，而非值相同。常用方法有两种：一是哈希集合法，遍历链表A将节点存入集合，再遍历链表B检查节点是否已存在，时间复杂度O(m+n)，空间复杂度O(m)；二是双指针法，先计算两链表长度并让长链表指针先走长度差步，再同步遍历直至指针相遇或为空，时间复杂度O(m+n)，空间复杂度O(1)。双指针法更优，因无需额外空间。需注意边界情况：空链表不相交；尾节点不同则不相交；尾节点相同则必相交；交点可能在头节点或一链表为另一子链表。两种方法均基于节点身份比较，而非值比较，确保判断准确。
判断两个链表是否相交，核心在于它们是否共享同一个节点，而非仅仅节点的值相同。最常见且高效的方法有两种：一种是利用哈希集合（或称散列表）来记录遍历过的节点，另一种则是巧妙地运用双指针，在不使用额外空间的情况下找出交点。理解这两种方法，以及它们各自的优劣，对于解决这类链表问题至关重要。
解决方案
在我看来，解决链表相交问题，双指针法无疑是最为优雅且空间复杂度最优的方案。它不需要任何额外的存储空间，仅仅通过指针的移动就能找到答案。
这个方法的大致思路是这样的：假设我们有两个链表A和B。
计算长度并对齐：我们先分别遍历链表A和链表B，计算出它们的长度
lenA
和
lenB
。同时，在遍历到末尾时，我们还可以顺便检查一下它们的尾节点是否相同。如果
headA
的尾节点和
headB
的尾节点不同，那它们肯定不相交，直接返回
null
就行了。这个小技巧能帮我们快速排除掉很多不相交的情况，挺实用的。
如果尾节点相同，那它们就可能相交了。接下来，我们要让两个链表从“同一起跑线”开始遍历。找出两个链表的长度差
diff = abs(lenA - lenB)
。然后，让较长的那个链表的头指针先向前移动
diff
步。这样一来，两个链表的当前指针就和它们的交点（如果存在的话）保持了相同的距离。
同步遍历寻找交点：现在，两个指针（一个在链表A上，一个在链表B上）已经“对齐”了。我们让它们以相同的速度，一步一步地向前移动。在每次移动之后，都比较这两个指针指向的节点是否是同一个。一旦
pointerA == pointerB
，那么这个节点就是它们的第一个交点。我们直接返回这个节点。如果两个指针都走到了链表末尾（即都变成了
null
）还没相遇，那就说明它们虽然尾节点相同，但实际上并没有相交（这种情况通常不会发生，因为如果尾节点相同，它们必然会在某个地方相交）。但为了逻辑严谨，我们也可以在循环结束后返回
null
。
用伪代码来描述一下，大概是这样：
class ListNode: def __init__(self, x): self.val = x self.next = Nonedef getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode: if not headA or not headB: return None # 1. 计算长度并找到尾节点 currA, lenA = headA, 0 while currA.next: currA = currA.next lenA += 1 lenA += 1 # 加上最后一个节点 currB, lenB = headB, 0 while currB.next: currB = currB.next lenB += 1 lenB += 1 # 加上最后一个节点 # 如果尾节点不同，则不相交 if currA != currB: return None # 2. 对齐链表头 ptrA, ptrB = headA, headB if lenA > lenB: for _ in range(lenA - lenB): ptrA = ptrA.next elif lenB > lenA: for _ in range(lenB - lenA): ptrB = ptrB.next # 3. 同步遍历寻找交点 while ptrA != ptrB: ptrA = ptrA.next ptrB = ptrB.next return ptrA # 此时ptrA和ptrB指向同一个交点，或者都为None（如果一开始就相同）
这个方法的时间复杂度是 O(m+n)，因为我们需要遍历两个链表两次（一次计算长度，一次寻找交点），但空间复杂度是 O(1)，这是它最大的优势。
为什么不能仅仅通过节点的值来判断相交？
这个问题我记得刚接触链表的时候，就挺让我着迷的，也经常看到有朋友在这里犯迷糊。简单来说，判断链表是否相交，我们看的是它们是否共享“同一个物理节点”，也就是内存地址完全一致的那个对象，而不是仅仅节点里面存储的
val
值是不是一样。
想想看，如果两个链表各自有一个节点，它们的值都是
5
，但它们是两个完全独立的节点对象，在内存里占据不同的位置，那它们显然不能算作相交。相交的定义是，从某个节点开始，它们后面的所有节点都是一模一样的，就像两条路汇合成了一条路。如果只比较值，你可能会遇到两个完全独立的链表，它们有很多节点的值都碰巧一样，但它们从未真正“合并”过。
举个例子：链表A: 1 -> 2 -> 3链表B: 1 -> 2 -> 4
这里面，A和B都有值是1和2的节点。但它们是各自独立的节点。如果我们只看值，可能会误以为它们在1或2处相交了，但实际上并没有。它们是两条完全分开的路径。
所以，核心是“对象身份”的比较，而非“值”的比较。这也是为什么在代码里我们判断的是
ptrA == ptrB
，而不是
ptrA.val == ptrB.val
。搞清楚这一点，对于理解链表这种数据结构的本质，我觉得挺重要的。
链表相交的常见误区与边界情况
在处理链表相交问题时，除了前面提到的“只比较值”这个误区，还有一些边界情况和思路上的小陷阱，我觉得也值得聊聊。
空链表： 如果其中一个链表是空的（
headA
或
headB
为
null
），它们显然不可能相交。这时候直接返回
null
就行了。这是最简单的边界情况，但有时容易在写代码时漏掉。不相交但尾节点不同： 大多数不相交的链表，它们的尾节点也肯定是不同的。在这种情况下，我们前面双指针法里提到的“先检查尾节点”的优化就能派上用场了。如果尾节点不同，直接判断不相交，省去了后续的遍历。这算是一个小小的性能提升点。不相交但尾节点相同？ 这个听起来有点矛盾，但实际上是不存在的。如果两个链表真的在某个点相交了，那么从那个交点往后，它们就是同一条链表了，自然它们的尾节点也必须是同一个。所以，如果尾节点不同，它们必然不相交；如果尾节点相同，它们必然相交。这个逻辑关系非常重要。相交在头节点： 有时候两个链表可能在它们的第一个节点就相交了，也就是
headA == headB
。这种情况下，我们的双指针法也能正确处理，因为它会直接在第一步就发现
ptrA == ptrB
并返回这个头节点。一个链表是另一个的子链表： 比如链表A是
1 -> 2 -> 3
，链表B是
2 -> 3
，并且B的头节点
2
就是A的第二个节点
2
。这种也算相交，并且交点就是
2
。我们的双指针法同样能正确识别。
理解这些边界情况，能帮助我们在设计算法时考虑得更周全，避免一些意想不到的bug。说到底，链表操作，细节决定成败。
空间换时间：哈希集合的策略
虽然我个人更偏爱双指针的优雅，但哈希集合（或者说用
Set
结构）来解决链表相交问题，在某些场景下，比如面试时想快速给出一个正确答案，或者对空间复杂度不那么敏感时，它是一个非常直观且易于实现的好方法。
它的核心思想很简单：
遍历并存储一个链表的所有节点：我们选择其中一个链表（比如链表A），从头开始遍历它。每遍历到一个节点，就把这个节点本身（也就是它的内存地址引用）存储到一个哈希集合里。哈希集合的特点就是查找效率非常高，通常是 O(1) 的平均时间复杂度。
遍历另一个链表并查找：接着，我们开始遍历另一个链表（比如链表B）。对于链表B的每一个节点，我们都去哈希集合里查询一下，看看这个节点是否已经存在。如果找到了，那恭喜你，这个节点就是两个链表的第一个交点。我们直接返回它。如果遍历完链表B的所有节点，都没有在哈希集合里找到任何一个节点，那就说明这两个链表不相交，返回
null
。
用伪代码表示：
def getIntersectionNodeWithHashSet(headA: ListNode, headB: ListNode) -> ListNode: if not headA or not headB: return None visited_nodes = set() # 创建一个哈希集合 # 遍历链表A，将所有节点加入哈希集合 currA = headA while currA: visited_nodes.add(currA) currA = currA.next # 遍历链表B，查找是否存在于哈希集合中 currB = headB while currB: if currB in visited_nodes: # 如果找到，说明相交 return currB currB = currB.next return None # 遍历完B也没找到，说明不相交
优缺点分析：
优点：实现简单直观： 逻辑非常清晰，不容易出错。时间复杂度优秀： 同样是 O(m+n)，因为需要遍历两个链表一次，哈希集合的插入和查找操作平均是 O(1)。缺点：空间复杂度较高： 需要额外的 O(m) 或 O(n) 空间来存储一个链表的所有节点。对于内存敏感的场景，这可能是一个问题。
所以，在选择解决方案时，如果对空间有严格要求，双指针法是首选；如果更看重代码的简洁性和开发效率，或者空间不是瓶颈，哈希集合法也是一个非常不错的选择。这两种方法各有千秋，理解它们背后的原理和适用场景，才能在实际问题中做出最合适的选择。
以上就是如何判断两个链表是否相交？的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1370017.html
微信扫一扫 
支付宝扫一扫 
