两个链表的第一个公共结点

---

题目描述

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

解题思路

第一个公共结点，即从某个结点开始，两个链表指针指向的地址都是相同的。

解决这个问题有两个方法：

方法一：

​ 可以把两个链表拼接起来，链表A在前链表B在后，另一种拼接方法是链表B在前链表A在后。然后同时遍历两个这两个链表，就能找到公共结点。时间复杂度为O(m+n), 空间复杂度O(m+n).

方法二：

可以先把长的链表的头砍掉，让两个链表的长度相同，然后再同时遍历，也能找到公共结点。时间复杂度为 O(m+n), 空间复杂度为 O(max（m，n)）。

代码

struct ListNode
{
    int val;
    struct ListNode* next;
    ListNode (int x): bal(x), next(NULL) {}
};
class Solution
{
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2)
    {
        if (pHead1 == NULL || pHead2 == NULL)
            return NULL;
        int len1 = getLength(pHead1); // pHead1链表长度
        int len2 = getLength(pHead2);// pHead2链表长度
        
        ListNode* LongList = pHead1;
        ListNode* ShortList = pHead2;
        int OverList = len1 - len2;
        if (len1 < len2) // 假如pHead1的长度小于pHead2的长度
        {
            ListNode* LongList = pHead2;
            ListNode* ShortList = pHead1;
            int OverList = len2 - len1;
        }
        
        // 砍掉长链表的多出的部分
        for (int i = 0; i < OverList; i++)
            LongList = LongList->next;
        
        while (LongList != NULL && ShortList != NULL && LongList != ShortList)
        {
            LongList = LongList->next;
            ShortList = ShortList->next;
        }
        return LongList;
    }
    
    int getLength(ListNode* pHead)
    {
        if (pHead == NULL)
            return o;
        
        int count = 0;
        while (pHead != NULL)
        {
            pHead = pHead->next;
            count++;
        }
        return count;
    }
};

参考博文链接：https://cuijiahua.com/blog/2018/01/basis_36.html