- 搜標(biāo)題
- 搜題干
- 搜選項
問答題
面試題:反轉(zhuǎn)鏈表題目：定義一個函數(shù)，輸入一個鏈表的頭結(jié)點，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭結(jié)點。面試題:反轉(zhuǎn)鏈表 題目：定義一個函數(shù)，輸入一個鏈表的頭結(jié)點，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭結(jié)點。鏈表結(jié)點定義如下： struct List Node { int m_n Key ListNode+ m_p Next }；
答案：
解決與鏈表相關(guān)的問題總是有大量的指針操作，而指針操作的代碼總是容易出錯的。很多面試官喜歡出鏈表相關(guān)的問題，就是想通過指針操作來考查應(yīng)聘者的編碼功底。為了避免出錯，我們最好先進行全面的分析。在實際軟件開發(fā)周期中，設(shè)計的時間通常不會比編碼的時間短。在面試的時候我們不要急于動手寫代碼，而是一開始仔細(xì)分析和設(shè)計，這將會給面 試官留下很好的印象。與其很快寫出一段漏洞百出的代碼，倒不如仔細(xì)分析再寫出魯棒的代碼。 為了正確地反轉(zhuǎn)一個鏈表，需要調(diào)整鏈表中指針的方向。為了將調(diào)整指針這個復(fù)雜的過程分析清楚，我們可以借助圖形來直觀地分析。在圖3．6（a）所示的鏈表中，h、i和j是3個相鄰的結(jié)點。假設(shè)經(jīng)過若干操作，我們已經(jīng)把結(jié)點h之前的指針調(diào)整完畢，這些結(jié)點的m_pNext都指向前面一個結(jié)點。接下來我們把i的m_pNext指向h，此時的鏈表結(jié)構(gòu)如圖3．6（b） 所示。 圖3．6反轉(zhuǎn)鏈表中結(jié)點的m_pNext指針導(dǎo)致鏈表出現(xiàn)斷裂 注：（a） 一個鏈表。（b）把i之前所有的結(jié)點的m_pNext都指向前一個結(jié)點，導(dǎo)致鏈表在結(jié)點i、j之間斷裂。 不難注意到，由于結(jié)點i的m_pNext指向了它的前一個結(jié)點，導(dǎo)致我們無法在鏈表中遍歷到結(jié)點j。為了避免鏈表在結(jié)點i處斷開，我們需要在調(diào)整結(jié)點i的m_pNext之前，把結(jié)點j保存下來。 也就是說我們在調(diào)整結(jié)點i的m_pNext指針時，除了需要知道結(jié)點i本身之外，還需要i的前一個結(jié)點h，因為我們需要把結(jié)點i的m_p Next指向結(jié)點h。同時，我們還事先需要保存i的一個結(jié)點j，以防止鏈表斷開。因此相應(yīng)地我們需要定義3個指針，分別指向當(dāng)前遍歷到的結(jié)點、它的前一個結(jié)點及后一個結(jié)點。 最后我們試著找到反轉(zhuǎn)后鏈表的頭結(jié)點。不難分析出反轉(zhuǎn)后鏈表的頭結(jié)點是原始鏈表的尾結(jié)點。什么結(jié)點是尾結(jié)點？自然是m_pNext為NULL的結(jié)點。 有了前面的分析，我們不難寫出如下代碼： ListNode* Reverselist（ListNode*p Head） { ListNode+ pReversedHead=NULL; ListNode+- pNode=p Head; listNode*x pPrev=NULL while （pNode !=NULL） { ListNode*pNext=pNode->m_p Next; if （pNext==NULL） pReversedHead=p Node; pNode->m_ pNext - pprew; pPrev=pNode; pNode=pNext; } return pReversedHead; } ______________________________________________________ 在面試的過程中，我們發(fā)現(xiàn)應(yīng)聘者的代碼中經(jīng)常出現(xiàn)如下3種問題： ● 輸入的鏈表頭指針為NULL或者整個鏈表只有一個結(jié)點時，程序立即崩潰。 ● 反轉(zhuǎn)后的鏈表出現(xiàn)斷裂。 ● 返回的反轉(zhuǎn)之后的頭結(jié)點不是原始鏈表的尾結(jié)點。 在實際面試的時候，不同應(yīng)聘者的思路各不相同，因此寫出的代碼也不一樣。那么應(yīng)聘者如何才能及時發(fā)現(xiàn)并糾正代碼中的問題，以確保不犯上述錯誤呢？一個很好的辦法就是提前想好測試用例。在寫出代碼之后，立即用事先準(zhǔn)備好的測試用例檢查測試。如果面試是以手寫代碼的方式，那也要在心里默默運行代碼做單元測試。只有確保代碼通過測試之后，再提交面試官。我們要記住一點：自己多花時間找出問題并修正問題，比在面試官找出問題之后再去慌慌張張修改代碼要好得多。其實面試官檢查應(yīng)聘者代碼的方法也是用他事先準(zhǔn)備好的測試用例來測試。如果應(yīng)聘者能夠想到這些測試用例，并用它們來檢查測試自己的代碼，那就能保證有備無患、萬無一失了。 以這道題為例，我們至少應(yīng)該想到幾類測試用例對代碼做功能測試： ● 輸入的鏈表頭指針是NULL。 ● 輸入的鏈表只有一個結(jié)點。 ● 輸入的鏈表有多個結(jié)點。 如果我們確信代碼能夠通過這3類測試用例的測試，那我們就有很大的把握能夠通過這輪面試了。 源代碼： 本題完整的源代碼詳見1 6_ ReverseList項目。 測試用例： ● 功能測試（輸入的鏈表含有多個結(jié)點，鏈表中只有一個結(jié)點）。 ● 特殊輸入測試（鏈表頭結(jié)點為NULL指針）。 本題考點： ● 考查應(yīng)聘者對鏈表、指針的編程能力。 ● 特別注重考查應(yīng)聘者思維的全面性及寫出來的代碼的魯棒性。 本題擴展： 用遞歸實現(xiàn)同樣的反轉(zhuǎn)鏈表的功能。
