程序員面試題之兩鏈表的第一個公共結點[數據結構]
題目:兩個單向鏈表,找出它們的第一個公共結點。
鏈表的結點定義爲:
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
// nodes, return NULL
///////////////////////////////////////////////////////////////////////
ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2)
{
// Get the length of two lists
unsigned int nLength1 = ListLength(pHead1);
unsigned int nLength2 = ListLength(pHead2);
int nLengthDif = nLength1 - nLength2;
// Get the longer list
ListNode *pListHeadLong = pHead1;
ListNode *pListHeadShort = pHead2;
if(nLength2 > nLength1)
{
pListHeadLong = pHead2;
pListHeadShort = pHead1;
nLengthDif = nLength2 - nLength1;
}
// Move on the longer list
for(int i = 0; i < nLengthDif; ++ i)
pListHeadLong = pListHeadLong->m_pNext;
// Move on both lists
while((pListHeadLong != NULL) &&
(pListHeadShort != NULL) &&
(pListHeadLong != pListHeadShort))
{
pListHeadLong = pListHeadLong->m_pNext;
pListHeadShort = pListHeadShort->m_pNext;
}
// Get the first common node in two lists
ListNode *pFisrtCommonNode = NULL;
if(pListHeadLong == pListHeadShort)
pFisrtCommonNode = pListHeadLong;
return pFisrtCommonNode;
}
///////////////////////////////////////////////////////////////////////
// Get the length of list with head pHead
// Input: pHead - the head of list
// Return: the length of list
///////////////////////////////////////////////////////////////////////
unsigned int ListLength(ListNode* pHead)
{
unsigned int nLength = 0;
ListNode* pNode = pHead;
while(pNode != NULL)
{
++ nLength;
pNode = pNode->m_pNext;
}
return nLength;
}
-
面試心得體會(集錦15篇)15篇
當我們備受啓迪時,將其記錄在心得體會裏,讓自己銘記於心,這樣有利於我們不斷提升自我。但是心得體會有什麼要求呢?以下是小編爲大家整理的面試心得體會,僅供參考,歡迎大家閱讀。面試心得體會1在大家的共同努力下,我們組終於在笑聲中完成了對模擬面試的錄製。對於此次...
-
面試的注意事項(精選15篇)
面試的注意事項1當我們在一個崗位上時間過長,已經到達瓶頸階段不太能學到東西,自身也得不到提升之後,我們可能會開始考慮是否要跳槽換一個新環境以尋求一個更好的發展平臺。那麼,跳槽面試有沒有什麼特別需要注意的地方呢?下面就讓小編帶你去看看跳槽面試應該注意事...
-
面試自我優缺點介紹通用7篇
當進入一個陌生環境,我們有必要進行適當的自我介紹,用自我介紹往往可以向他人介紹自己。怎麼寫自我介紹才能避免踩雷呢?以下是小編收集整理的面試自我優缺點介紹,僅供參考,希望能夠幫助到大家。面試自我優缺點介紹1一般來講,面試自我介紹中我們都會說說自己的優點和...
-
銀行面試介紹
銀行面試介紹1各位考官:通過考試,今天,我以本崗位筆試第x的成績進入了面試。對我來說,這次工作機會顯得尤爲珍貴。我叫,今年27歲。x年7月我從xx學院系畢業。由於原因,使我與"太陽底下最光輝的職業"失之交臂。幸好,當時(原因),經人介紹,我在x單位有了工作經歷。回想起...