双指针法判断链表是否相交原理详解

如何判断两个链表是否相交？这是链表数据结构中一个经典问题，核心在于检测节点内存地址是否相同，而非节点值相同。本文深入探讨了两种常见的解决方案，并分析了各自的优劣。**哈希表法**通过遍历一个链表将节点存入哈希集合，再检查另一个链表的节点是否存在于该集合中，时间复杂度为O(m+n)，空间复杂度为O(m)。**双指针法**则更为巧妙，通过计算链表长度并移动指针，最终在交点相遇或同时到达末尾，时间复杂度同样为O(m+n)，但空间复杂度仅为O(1)，更节省空间。文章还详细分析了空链表、尾节点不同等边界情况，以及“值比较”的常见误区，并提供了Python代码示例，助你轻松掌握链表相交问题的解决方法，优化你的算法效率。

判断两个链表是否相交，核心是检测节点内存地址是否相同，而非值相同。常用方法有两种：一是哈希集合法，遍历链表A将节点存入集合，再遍历链表B检查节点是否已存在，时间复杂度O(m+n)，空间复杂度O(m)；二是双指针法，先计算两链表长度并让长链表指针先走长度差步，再同步遍历直至指针相遇或为空，时间复杂度O(m+n)，空间复杂度O(1)。双指针法更优，因无需额外空间。需注意边界情况：空链表不相交；尾节点不同则不相交；尾节点相同则必相交；交点可能在头节点或一链表为另一子链表。两种方法均基于节点身份比较，而非值比较，确保判断准确。

判断两个链表是否相交，核心在于它们是否共享同一个节点，而非仅仅节点的值相同。最常见且高效的方法有两种：一种是利用哈希集合（或称散列表）来记录遍历过的节点，另一种则是巧妙地运用双指针，在不使用额外空间的情况下找出交点。理解这两种方法，以及它们各自的优劣，对于解决这类链表问题至关重要。

解决方案

在我看来，解决链表相交问题，双指针法无疑是最为优雅且空间复杂度最优的方案。它不需要任何额外的存储空间，仅仅通过指针的移动就能找到答案。

这个方法的大致思路是这样的： 假设我们有两个链表A和B。

1. 计算长度并对齐： 我们先分别遍历链表A和链表B，计算出它们的长度 lenA 和 lenB。同时，在遍历到末尾时，我们还可以顺便检查一下它们的尾节点是否相同。如果 headA 的尾节点和 headB 的尾节点不同，那它们肯定不相交，直接返回 null 就行了。这个小技巧能帮我们快速排除掉很多不相交的情况，挺实用的。

   如果尾节点相同，那它们就可能相交了。 接下来，我们要让两个链表从“同一起跑线”开始遍历。找出两个链表的长度差 diff = abs(lenA - lenB)。然后，让较长的那个链表的头指针先向前移动 diff 步。这样一来，两个链表的当前指针就和它们的交点（如果存在的话）保持了相同的距离。

2. 同步遍历寻找交点： 现在，两个指针（一个在链表A上，一个在链表B上）已经“对齐”了。我们让它们以相同的速度，一步一步地向前移动。在每次移动之后，都比较这两个指针指向的节点是否是同一个。 一旦 pointerA == pointerB，那么这个节点就是它们的第一个交点。我们直接返回这个节点。 如果两个指针都走到了链表末尾（即都变成了 null）还没相遇，那就说明它们虽然尾节点相同，但实际上并没有相交（这种情况通常不会发生，因为如果尾节点相同，它们必然会在某个地方相交）。但为了逻辑严谨，我们也可以在循环结束后返回 null。

   用伪代码来描述一下，大概是这样：

   class ListNode:
       def __init__(self, x):
           self.val = x
           self.next = None
   
   def 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。搞清楚这一点，对于理解链表这种数据结构的本质，我觉得挺重要的。

链表相交的常见误区与边界情况

在处理链表相交问题时，除了前面提到的“只比较值”这个误区，还有一些边界情况和思路上的小陷阱，我觉得也值得聊聊。

1. 空链表： 如果其中一个链表是空的（headA 或 headB 为 null），它们显然不可能相交。这时候直接返回 null 就行了。这是最简单的边界情况，但有时容易在写代码时漏掉。
2. 不相交但尾节点不同： 大多数不相交的链表，它们的尾节点也肯定是不同的。在这种情况下，我们前面双指针法里提到的“先检查尾节点”的优化就能派上用场了。如果尾节点不同，直接判断不相交，省去了后续的遍历。这算是一个小小的性能提升点。
3. 不相交但尾节点相同？ 这个听起来有点矛盾，但实际上是不存在的。如果两个链表真的在某个点相交了，那么从那个交点往后，它们就是同一条链表了，自然它们的尾节点也必须是同一个。所以，如果尾节点不同，它们必然不相交；如果尾节点相同，它们必然相交。这个逻辑关系非常重要。
4. 相交在头节点： 有时候两个链表可能在它们的第一个节点就相交了，也就是 headA == headB。这种情况下，我们的双指针法也能正确处理，因为它会直接在第一步就发现 ptrA == ptrB 并返回这个头节点。
5. 一个链表是另一个的子链表： 比如链表A是 1 -> 2 -> 3，链表B是 2 -> 3，并且B的头节点 2 就是A的第二个节点 2。这种也算相交，并且交点就是 2。我们的双指针法同样能正确识别。

理解这些边界情况，能帮助我们在设计算法时考虑得更周全，避免一些意想不到的bug。说到底，链表操作，细节决定成败。

空间换时间：哈希集合的策略

虽然我个人更偏爱双指针的优雅，但哈希集合（或者说用 Set 结构）来解决链表相交问题，在某些场景下，比如面试时想快速给出一个正确答案，或者对空间复杂度不那么敏感时，它是一个非常直观且易于实现的好方法。

它的核心思想很简单：

1. 遍历并存储一个链表的所有节点： 我们选择其中一个链表（比如链表A），从头开始遍历它。每遍历到一个节点，就把这个节点本身（也就是它的内存地址引用）存储到一个哈希集合里。哈希集合的特点就是查找效率非常高，通常是 O(1) 的平均时间复杂度。

2. 遍历另一个链表并查找： 接着，我们开始遍历另一个链表（比如链表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) 空间来存储一个链表的所有节点。对于内存敏感的场景，这可能是一个问题。

所以，在选择解决方案时，如果对空间有严格要求，双指针法是首选；如果更看重代码的简洁性和开发效率，或者空间不是瓶颈，哈希集合法也是一个非常不错的选择。这两种方法各有千秋，理解它们背后的原理和适用场景，才能在实际问题中做出最合适的选择。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《双指针法判断链表是否相交原理详解》文章吧，也可关注golang学习网公众号了解相关技术文章。