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

　　-反轉鏈表

　　題目：輸入一個鏈表的頭結點，反轉該鏈表，并返回反轉后鏈表的頭結點。鏈表結點定義如下：

　　struct ListNode

　　{

　　int m_nKey;

　　ListNode* m_pNext;

　　};

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

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

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

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

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

　　aßbß…lßm nà…

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

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

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

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

　　// 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)。

　　相關推薦：

　　2015年軟考信息技術處理員考前知識點總結匯總

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

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