描述

题目描述

输入两个无环的单链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

示例

输入：{1,2,3},{4,5},{6,7}
返回值：{6,7}
说明：
第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的

引言

很多题目想不出解法，要学会抠题目描述的字眼，有可能是看错了或者看少了，导致理解错了题意。

还有很重要的一点：关于链表的题目和二叉树、图等等题目，最好在纸上画图，帮助快速理解题目。

知识点：链表，双指针，画图
难度：⭐⭐

题解

解题思路

题目要求是两无环单链表找出第一个公共节点，有关链表就逃不开对指针的灵活应用和一些扩展应用，如：双指针、快慢指针等

本题最容易想到的就是采用双指针同速移动的方法，求出第一个公共节点

方法一：双同速指针

图解

算法流程：

使用两个指针分别从两个链表头节点出发
两个指针分别走完当前链表后，再从另一个链表重新开始走，直到相遇
当他们走的步数刚好相等时，两个指针第一次相遇

Java 版本代码如下：

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        // 双指针
        ListNode pA = pHead1, pB = pHead2;
        // 一直走，直到相遇
        while(pA != pB) {
            // 两个指针分别走完当前链表后，再从另一个链表重新开始走，直到相遇
            // 当他们走的步数刚好相等时，两个指针第一次相遇
            pA = (pA == null ? pHead2 : pA.next); 
            pB = (pB == null ? pHead1 : pB.next); 
        }
        return pA;
    }
}

Python 版本代码如下：

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        pA, pB = pHead1, pHead2
        # 一直走，直到相遇
        while pA!= pB:
            # 两个指针分别走完当前链表后，再从另一个链表重新开始走，直到相遇
            # 当他们走的步数刚好相等时，两个指针第一次相遇
            pA = pA.next if pA else pHead2
            pB = pB.next if pB else pHead1
        return pA

复杂度分析：

时间复杂度 O(a+b)：最差情况下：假设两个链表节点数分别为 a 和 b，两个链表节点数只相差 1，需遍历 a + b 个节点。
空间复杂度 O(1)：双指针指针只需使用常数大小的额外空间

两个链表的第一个公共结点(双同速指针相遇)

描述