數(shù)據(jù)結(jié)構(gòu) —— 反轉(zhuǎn)鏈表?

反轉(zhuǎn)鏈表[數(shù)據(jù)結(jié)構(gòu)]

輸入一個鏈表的頭結(jié)點（已報名左程云算法和數(shù)據(jù)結(jié)構(gòu) 底部評），反轉(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)代碼總是容易出錯的，因此最好在動手寫程序之前作全面的分析。在面試的時候不急于動手而是一開始做仔細(xì)的分析和設(shè)計，將會給面試官留下很好的印象，因為在實際的軟件開發(fā)中，設(shè)計的時間總是比寫代碼的時間長。與其很快地寫出一段漏洞百出的代碼，遠(yuǎn)不如用較多的時間寫出一段健壯的代碼。

為了將調(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é)點?，F(xiàn)在我們遍歷到結(jié)點m。當(dāng)然，我們需要把調(diào)整結(jié)點的m_pNext指針讓它指向結(jié)點l。但注意一旦調(diào)整了指針的指向，鏈表就斷開了