两个链表第一个公共结点

1 题目

输入两个链表，找出它们的第一个公共结点。
时间限制：1s；空间限制：32768K

2 思路描述

使用两个指针 分别指向两个链表的第一个结点 。将分为以下几种情况：

1. 当两个链表长度相等，且有公共结点时，两个指针同时后移，会找到第一个公共节点。当 时退出。

长度相等，有公共结点.jpg

2. 当两个链表长度相等，且没有公共结点时，两个指针同时后移，直到两个指针都指向 None 退出。

长度相等，没有公公结点.jpg

3. 当两个链表长度不等，且有公共结点时，两个指针同时后移，当 指向 None 后，将其重新指向第二个链表的第一个结点 。当 指向 None 后，将其重新指向第一个链表的第一个结点 。当 时退出。

长度不等，有公共结点.jpg

4. 当两个链表长度不等，且没有公共结点时，两个指针同时后移，当 指向 None 后，将其重新指向第二个链表的第一个结点 。当 指向 None 后，将其重新指向第一个链表的第一个结点 。当 时退出。

长度不等，没有公共结点.jpg

---

3 程序代码：

class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        if not pHead1 or not pHead2:  
            return None  
        p1, p2 = pHead1, pHead2  
        while p1 != p2:  
            p1 = (pHead2 if not p1 else p1.next)  
            p2 = (pHead1 if not p2 else p2.next)
        return p1