LeetCode 160. 相交链表（超详细超容易理解的动画解法！！！）

傷城~ 2022-10-22 10:59 4阅读 0赞

大家好，我是程序员吴师兄，今天给大家图解的题目是 LeetCode 第 160 号问题：**相交链表**。

更多题目图解请访问网站：https://www.algomooc.com

# 一、题目描述 #

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

![cc0635c584ea066bd5bad316d0f8c9e9.png][]

在节点 c1 开始相交。

**注意：**

*  如果两个链表没有交点，返回 null。
 *  在返回结果后，两个链表仍须保持原有的结构。
 *  可假定整个链表结构中没有循环。
 *  程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

# 二、题目解析 #

为了方便理解，假设链表 A 的节点数为 a，链表 B 的节点数为 b，两链表的公共尾部节点数为 c ，第一个公共节点为 `c1`。

![1346ca0f7a10a4921d32ee5f22f79180.png][]

让指针 `PA` 和 `pB` 分别指向链表 A 和链表 B 的头结点，之后两个指针分别以步幅为 1 的速度向链表的尾部遍历。

*  当指针 `pA` 遍历到链表 A 的尾节点时，此时指针 `pA` 走了 a 个节点，将指针 `pA` 指向链表 B 的头部，继续向后遍历，直至走到 `c1`，此时指针 `PA` 总共走了 `a + ( b - c )` 步。
 *  当指针 `pB` 遍历到链表 B 的尾节点时，此时指针 `pB` 走了 b 个节点，将指针 `pB` 指向链表 A 的头部，继续向后遍历，直至走到 `c1`，此时指针 `PB` 总共走了 `b + ( a - c )` 步。

根据数学知识，`a + ( b - c ) = b + ( a - c )` ，如果 c > 0，表明两链表有公共尾部， `c1` 存在，两两链表同时到达 `c1`；如果 c = 0，表明两链表没有公共尾部，指针 `PA` 和 `pB` 都指向 `NULL`。

# 三、动画理解 #

# 四、参考代码 #

// 登录 https://www.algomooc.com 查看更多图解
    public ListNode getInterpNode(ListNode headA, ListNode headB) {
    
        // 边界判断
        if (headA == null || headB == null) return null;
        
        ListNode pA = headA, pB = headBA
        
        //指针 PA 和 指针 PB 不断向后遍历，直到找到相交点
        while (pA != pB) {
            // 指针 PA 一开始在链表 A 上遍历，当走到链表 A 的尾部即 null 时，跳转到链表 B 上 
            pA = pA == null ? headB : pA.next;
            // 指针 PB 一开始在链表 B 上遍历，当走到链表 B 的尾部即 null 时，跳转到链表 A 上 
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

# 五、复杂度分析 #

#### 时间复杂度 ####

时间复杂度为 O( a + b )，两个链表没有公共节点。

#### 空间复杂度 ####

空间复杂度为 O(1)。

[cc0635c584ea066bd5bad316d0f8c9e9.png]: /images/20221022/05f8893603fa40caa8cd128ba5d41a81.png
[1346ca0f7a10a4921d32ee5f22f79180.png]: /images/20221022/4cef3c92ca854cd1a80a33026c4c39e5.png