查看匯總：2015軟件水平考試程序員精選題匯總

　　-反轉(zhuǎn)鏈表

　　題目：輸入一個鏈表的頭結(jié)點(diǎn)，反轉(zhuǎn)該鏈表，并返回反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)。鏈表結(jié)點(diǎn)定義如下：

　　struct ListNode

　　{

　　int m_nKey;

　　ListNode* m_pNext;

　　};

　　分析：這是一道廣為流傳的微軟面試題。由于這道題能夠很好的反應(yīng)出程序員思維是否嚴(yán)密，在微軟之后已經(jīng)有很多公司在面試時采用了這道題。

　　為了正確地反轉(zhuǎn)一個鏈表，需要調(diào)整指針的指向。與指針操作相關(guān)代碼總是容易出錯的，因此最好在動手寫程序之前作全面的分析。在面試的時候不急于動手而是一開始做仔細(xì)的分析和設(shè)計(jì)，將會給面試官留下很好的印象，因?yàn)樵趯?shí)際的軟件開發(fā)中，設(shè)計(jì)的時間總是比寫代碼的時間長。與其很快地寫出一段漏洞百出的代碼，遠(yuǎn)不如用較多的時間寫出一段健壯的代碼。

　　為了將調(diào)整指針這個復(fù)雜的過程分析清楚，我們可以借助圖形來直觀地分析。假設(shè)下圖中l(wèi)、m和n是三個相鄰的結(jié)點(diǎn)：

　　aßbß…ßl mànà…

　　假設(shè)經(jīng)過若干操作，我們已經(jīng)把結(jié)點(diǎn)l之前的指針調(diào)整完畢，這些結(jié)點(diǎn)的m_pNext指針都指向前面一個結(jié)點(diǎn)。現(xiàn)在我們遍歷到結(jié)點(diǎn)m。當(dāng)然，我們需要把調(diào)整結(jié)點(diǎn)的m_pNext指針讓它指向結(jié)點(diǎn)l。但注意一旦調(diào)整了指針的指向，鏈表就斷開了，如下圖所示：

　　aßbß…lßm nà…

　　因?yàn)橐呀?jīng)沒有指針指向結(jié)點(diǎn)n，我們沒有辦法再遍歷到結(jié)點(diǎn)n了。因此為了避免鏈表斷開，我們需要在調(diào)整m的m_pNext之前要把n保存下來。

　　接下來我們試著找到反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)。不難分析出反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)是原始鏈表的尾位結(jié)點(diǎn)。什么結(jié)點(diǎn)是尾結(jié)點(diǎn)?就是m_pNext為空指針的結(jié)點(diǎn)。

　　基于上述分析，我們不難寫出如下代碼：

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

　　// Reverse a list iteratively

　　// Input: pHead - the head of the original list

　　// Output: the head of the reversed head

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

　　ListNode* ReverseIteratively(ListNode* pHead)

　　{

　　ListNode* pReversedHead = NULL;

　　ListNode* pNode = pHead;

　　ListNode* pPrev = NULL;

　　while(pNode != NULL)

　　{

　　// get the next node, and save it at pNext

　　ListNode* pNext = pNode->m_pNext;

　　// if the next node is null, the currect is the end of original

　　// list, and it's the head of the reversed list

　　if(pNext == NULL)

　　pReversedHead = pNode;

　　// reverse the linkage between nodes

　　pNode->m_pNext = pPrev;

　　// move forward on the the list

　　pPrev = pNode;

　　pNode = pNext;

　　}

　　return pReversedHead;

　　}

　　擴(kuò)展：本題也可以遞歸實(shí)現(xiàn)。

　　相關(guān)推薦：

　　2015年軟考信息技術(shù)處理員考前知識點(diǎn)總結(jié)匯總

　　2015年軟件水平考試《程序員》提高練習(xí)題匯總

　　2015軟件水平考試《程序員》知識點(diǎn)總結(jié)匯總