程序員面試題精選100題(35)-兩鏈表的第一個公共結點[數據結構]

時間:2019-09-22 編輯:范文亭

題目:兩個單向鏈表,找出它們的第一個公共結點。

鏈表的結點定義為:

struct ListNode

{

      int         m_nKey;

      ListNode*   m_pNext;

};

分析:這是一道微軟的面試題。微軟非常喜歡與鏈表相關的題目,因此在微軟的面試題中,鏈表出現的概率相當高。

如果兩個單向鏈表有公共的結點,也就是說兩個鏈表從某一結點開始,它們的m_pNext都指向同一個結點。但由于是單向鏈表的結點,每個結點只有一個m_pNext,因此從第一個公共結點開始,之后它們所有結點都是重合的,不可能再出現分叉。所以,兩個有公共結點而部分重合的鏈表,拓撲形狀看起來像一個Y,而不可能像X

看到這個題目,第一反應就是蠻力法:在第一鏈表上順序遍歷每個結點。每遍歷一個結點的時候,在第二個鏈表上順序遍歷每個結點。如果此時兩個鏈表上的結點是一樣的,說明此時兩個鏈表重合,于是找到了它們的公共結點。如果第一個鏈表的長度為m,第二個鏈表的長度為n,顯然,該方法的時間復雜度為O(mn)

接下來我們試著去尋找一個線性時間復雜度的算法。我們先把問題簡化:如何判斷兩個單向鏈表有沒有公共結點?前面已經提到,如果兩個鏈表有一個公共結點,那么該公共結點之后的所有結點都是重合的。那么,它們的最后一個結點必然是重合的。因此,我們判斷兩個鏈表是不是有重合的部分,只要分別遍歷兩個鏈表到最后一個結點。如果兩個尾結點是一樣的,說明它們用重合;否則兩個鏈表沒有公共的結點。

在上面的思路中,順序遍歷兩個鏈表到尾結點的時候,我們不能保證在兩個鏈表上同時到達尾結點。這是因為兩個鏈表不一定長度一樣。但如果假設一個鏈表比另一個長l個結點,我們先在長的鏈表上遍歷l個結點,之后再同步遍歷,這個時候我們就能保證同時到達最后一個結點了。由于兩個鏈表從第一個公共結點考試到鏈表的尾結點,這一部分是重合的。因此,它們肯定也是同時到達第一公共結點的。于是在遍歷中,第一個相同的結點就是第一個公共的結點。

在這個思路中,我們先要分別遍歷兩個鏈表得到它們的長度,并求出兩個長度之差。在長的鏈表上先遍歷若干次之后,再同步遍歷兩個鏈表,知道找到相同的結點,或者一直到鏈表結束。此時,如果第一個鏈表的長度為m,第二個鏈表的長度為n,該方法的時間復雜度為O(m+n)

基于這個思路,我們不難寫出如下的代碼:

///////////////////////////////////////////////////////////////////////

// Find the first common node in the list with head pHead1 and

// the list with head pHead2

// Input: pHead1 - the head of the first list

//        pHead2 - the head of the second list

// Return: the first common node in two list. If there is no common

本文已影響
相關文章
大亨pk10计划苹果版