面試題：兩個連結清單的第一個公共結點

題目描述： 輸入兩個連結清單，求他們的第一個公共結點。

（圖中内容不是測試用例的數字）

第一種思路描述：

1. 首先周遊兩個連結清單，得到其長度gap
2. 接着，讓較長的連結清單先走gap步

3. 兩個連結清單同時走，此時找到的第一個公共結點就是所需結點

   時間複雜度O（m+n）

   代碼實作：

//此處借用了連結清單的頭檔案
//擷取連結清單長度
int GetListLength(SListNode* list)
{
    assert(list);
    int count = ;
    SListNode* node = list;
    while (node != NULL)
    {
        count++;
        node = node->_next;

    }
    return count;
}

SListNode* FindFirstCommonNode(SListNode* list1, SListNode* list2)
{
    {
        SListNode* longlist = NULL;
        SListNode* shortlist = NULL;
        SListNode* cur1 = list1;
        SListNode* cur2 = list2;
        int n1 =GetListLength(cur1);
        int n2 = GetListLength(cur2);
        int gap = ;

        longlist = list1;
        shortlist = list2;

        //比較兩個連結清單的大小
        if (n1 < n2)
        {
            longlist = list2;
            shortlist = list1;
        }
        gap = abs(n1 - n2);//絕對值
        //長連結清單先走gap步，短連結清單，長連結清單再同時繼續走
        while (gap--)
        {
            longlist = longlist->_next;
        }
        while (shortlist != longlist)
        {
            shortlist = shortlist->_next;
            longlist = longlist->_next;
        }
        return shortlist;
    }
}
int main()
{
    SListNode* node11, *node22;
    SListNode* node1 = BuySListNode();
    SListNode* node2 = BuySListNode();
    SListNode* node3 = BuySListNode();
    SListNode* node4 = BuySListNode();
    SListNode* node5 = BuySListNode();
    node1->_next = node2;
    node2->_next = node3;
    node3->_next = node4;
    node4->_next = node5;

    node11 = BuySListNode();
    node22 = BuySListNode();
    node11->_next = node22;
    node22->_next = node4;

    printf("Cross Node? %d\n", FindFirstCommonNode(node1,node11)->_data);
    system("pause");
    return ;
}
           

截圖我就不粘貼了，結果為4,。

同樣也可借助棧實作，時間複雜度也是O（m+n）,不過空間效率較上者低。

第二種思路：分别将兩個連結清單放入兩個棧裡，此時兩個連結清單的尾結點位于棧頂，接下來比較結點是否相同，如果相同，彈出，接着比較下一個結點，直至找到最後一個相同的結點，列印之。，空間複雜度O（m+n）.相當于用空間換取時間。