如何判断两个链表是否相交？-Python教程-PHP中文网

判断两个链表是否相交，核心是检测节点内存地址是否相同，而非值相同。常用方法有两种：一是哈希集合法，遍历链表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 = 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

登录后复制

值是不是一样。

想想看，如果两个链表各自有一个节点，它们的值都是

登录后复制

，但它们是两个完全独立的节点对象，在内存里占据不同的位置，那它们显然不能算作相交。相交的定义是，从某个节点开始，它们后面的所有节点都是一模一样的，就像两条路汇合成了一条路。如果只比较值，你可能会遇到两个完全独立的链表，它们有很多节点的值都碰巧一样，但它们从未真正“合并”过。

举个例子：链表A: 1 -> 2 -> 3 链表B: 1 -> 2 -> 4

这里面，A和B都有值是1和2的节点。但它们是各自独立的节点。如果我们只看值，可能会误以为它们在1或2处相交了，但实际上并没有。它们是两条完全分开的路径。

所以，核心是“对象身份”的比较，而非“值”的比较。这也是为什么在代码里我们判断的是

ptrA == ptrB

登录后复制

，而不是

ptrA.val == ptrB.val

登录后复制

。搞清楚这一点，对于理解链表这种数据结构的本质，我觉得挺重要的。

通义万相

通义万相，一个不断进化的AI艺术创作大模型

596

查看详情

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

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

空链表： 如果其中一个链表是空的（
```
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) 空间来存储一个链表的所有节点。对于内存敏感的场景，这可能是一个问题。

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

以上就是如何判断两个链表是否相交？的详细内容，更多请关注php中文网其它相关文章！