life02

題目：輸入一個鏈表的頭結點，反轉該鏈表，并返回反轉后鏈表的頭結點。鏈表結點定義如下：
struct ListNode
{
      int        m_nKey;
       ListNode* m_pNext;
};
分析：這是一道廣為流傳的微軟面試題。由于這道題能夠很好的反應出程序員思維是否嚴密，在微軟之后已經有很多公司在面試時采用了這道題。
為了正確地反轉一個鏈表，需要調整指針的指向。與指針操作相關代碼總是容易出錯的，因此最好在動手寫程序之前作全面的分析。在面試的時候不急于動手而是一開始做仔細的分析和設計，將會給面試官留下很好的印象，因為在實際的軟件開發中，設計的時間總是比寫代碼的時間長。與其很快地寫出一段漏洞百出的代碼，遠不如用較多的時間寫出一段健壯的代碼。
為了將調整指針這個復雜的過程分析清楚，我們可以借助圖形來直觀地分析。假設下圖中l、m和n是三個相鄰的結點：
aßbß…ßl  mànà…
假設經過若干操作，我們已經把結點l之前的指針調整完畢，這些結點的m_pNext指針都指向前面一個結點。現在我們遍歷到結點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;
}
（轉載

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

）