life02

題目：輸入一個(gè)鏈表的頭結(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)有很多公司在面試時(shí)采用了這道題。
為了正確地反轉(zhuǎn)一個(gè)鏈表，需要調(diào)整指針的指向。與指針操作相關(guān)代碼總是容易出錯(cuò)的，因此最好在動(dòng)手寫程序之前作全面的分析。在面試的時(shí)候不急于動(dòng)手而是一開(kāi)始做仔細(xì)的分析和設(shè)計(jì)，將會(huì)給面試官留下很好的印象，因?yàn)樵趯?shí)際的軟件開(kāi)發(fā)中，設(shè)計(jì)的時(shí)間總是比寫代碼的時(shí)間長(zhǎng)。與其很快地寫出一段漏洞百出的代碼，遠(yuǎn)不如用較多的時(shí)間寫出一段健壯的代碼。
為了將調(diào)整指針這個(gè)復(fù)雜的過(guò)程分析清楚，我們可以借助圖形來(lái)直觀地分析。假設(shè)下圖中l、m和n是三個(gè)相鄰的結(jié)點(diǎn)：
aßbß…ßl  mànà…
假設(shè)經(jīng)過(guò)若干操作，我們已經(jīng)把結(jié)點(diǎn)l之前的指針調(diào)整完畢，這些結(jié)點(diǎn)的m_pNext指針都指向前面一個(gè)結(jié)點(diǎn)?，F(xiàn)在我們遍歷到結(jié)點(diǎn)m。當(dāng)然，我們需要把調(diào)整結(jié)點(diǎn)的m_pNext指針讓它指向結(jié)點(diǎn)l。但注意一旦調(diào)整了指針的指向，鏈表就斷開(kāi)了，如下圖所示：
aßbß…lßm  nà…
因?yàn)橐呀?jīng)沒(méi)有指針指向結(jié)點(diǎn)n，我們沒(méi)有辦法再遍歷到結(jié)點(diǎn)n了。因此為了避免鏈表斷開(kāi)，我們需要在調(diào)整m的m_pNext之前要把n保存下來(lái)。
接下來(lái)我們?cè)囍业椒崔D(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;
}
（轉(zhuǎn)載

List ReverseList(List head)  
{  
    if(head->next == NULL || head->next->next == NULL)    
    {  
       return head;   /**//*鏈表為空或只有一個(gè)元素則直接返回*/  
    }  
  
    ListNode *t = NULL,  
             *p = head->next,  
             *q = head->next->next;  
    while(q != NULL)  
    {          
      t = q->next;  
      q->next = p;  
      p = q;  
      q = t;  
    }  
  
    /**//*此時(shí)q指向原始鏈表最后一個(gè)元素，也是逆轉(zhuǎn)后的鏈表的表頭元素*/  
    head->next->next = NULL;  /**//*設(shè)置鏈表尾*/  
    head->next = p;           /**//*調(diào)整鏈表頭*/  
    return head;  
}  
  

）