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

　　-反轉(zhuǎn)鏈表

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

　　struct ListNode

　　{

　　int m_nKey;

　　ListNode* m_pNext;

　　};

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

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

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

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

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

　　aßbß…lßm nà…

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

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

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

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

　　// 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;

　　}

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

　　相關(guān)推薦：

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

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

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