相交链表 | 秋招知识库

具体算法如下：

初始化两个指针 $p = headA, q = headB$ 。
不断循环，直到 $p = q$ 。
每次循环， $p$ 和 $q$ 各向后走一步。具体来说，如果 $p$ 不是空节点，那么更新 $p$ 为 $p . next$ ，否则更新 $p$ 为 $headB$ ；如果 $q$ 不是空节点，那么更新 $q$ 为 $q . next$ ，否则更新 $q$ 为 $headA$ 。
循环结束时，如果两条链表相交，那么此时 $p$ 和 $q$ 都在相交的起始节点处，返回 $p$ ；如果两条链表不相交，那么 $p$ 和 $q$ 都走到空节点，所以也可以返回 $p$ ，即空节点。

Python 解法1C++ 解法1

python

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        p, q = headA, headB
        while p is not q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* p = headA;
        ListNode* q = headB;
        while (p != q) {
            p = p ? p->next : headB;
            q = q ? q->next : headA;
        }
        return p;
    }
};

复杂度分析

时间复杂度： $O (m + n)$ ，其中 $m$ 是第一条链表的长度， $n$ 是第二条链表的长度。除了交点，每个节点会被指针 $p$ 访问至多一次，每个节点会被指针 $q$ 访问至多一次。
空间复杂度： $O (1)$ 。

更多相似题目，见下面的链表题单。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

复杂度分析 ​

分类题单 ​

复杂度分析

分类题单