【面試題】輸入兩個連結清單，找出他們的第一個公共結點

我們可以有如下步驟

• 先得到兩個連結清單的長度
• 知道較長的連結清單比 較短的連結清單多幾個節點
• 先在較長的連結清單上走若幹步
• 兩個連結清單上同時周遊，找到的第一個相同的結點就是他們的第一個公共結點。

  

  例如：得到兩個連結清單的長度分别為5和6，先讓長連結清單走1步，到結點4。接下來同時讓兩個連結清單分别從結點1和結點4走，直至找到結點6。

struct ListNode {
    int val;
    struct ListNode *next;
};
//輸入兩個連結清單，找出他們的第一個公共結點
int GetListLenth(ListNode *pHead)
{
    int len = ;
    ListNode *pNode = pHead;
    while (pNode != NULL)
    {
        ++len;
        pNode = pNode->next;
    }
    return len;
}
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) 
{
    //得到兩個連結清單的長度
    int len1 = GetListLenth(pHead1);
    int len2 = GetListLenth(pHead2);
    int lenth= len1 - len2;

    ListNode *pListLong = pHead1;
    ListNode *pListShort = pHead2;

    if (len2 > len1)
    {
        pListLong = pHead2;
        pListShort = pHead1;
        lenth = len2 - len1;

    }
    //先在長連結清單上走幾步，再同時周遊
    for (int i = ; i < lenth; ++i)
    {
        pListLong = pListLong->next;
    }
    while ((pListLong != NULL) && (pListShort != NULL) && (pListLong != pListShort))
    {
        pListLong = pListLong->next;
        pListShort = pListShort->next;
    }
    ListNode *pFirstCommon = pListLong;
    return pFirstCommon;
}