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

题目描述

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

问题分析

• 先判断两个链表哪个最长，计算长度差dif
• 让最长的链表先走dif步
• 然后两个链表同时走，判断如果指向同一个位置就说明到达了第一个公共结点

解题思路1

class Solution {
public:
    int getlength(ListNode* pHead)
    {
        int len = 0;
        while (pHead != nullptr)
        {
            len++;
            pHead = pHead->next;
        }
        return len;
    }

    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        
        unsigned int length1 = getlength(pHead1);
        unsigned int length2 = getlength(pHead2);
        int dif = length1 - length2;
        ListNode* longHead = pHead1;
        ListNode* shortHead = pHead2;
        if (dif < 0)
        {
            longHead = pHead2;
            shortHead = pHead1;
            dif = -dif;
        }
        for (int i = 0; i < dif; i++)
        {
            longHead = longHead->next;
        }
        while(longHead !=nullptr && shortHead !=nullptr && shortHead != longHead)
        {
            longHead = longHead->next;
            shortHead = shortHead->next;

        }
        return longHead;
    }
    
    
};