程序員面試題精選100題(19)-反轉鏈表

時間:2019-09-22 編輯:范文亭
程序員面試題精選100題(19)-反轉鏈表

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

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

另一種方法:以遞歸來實現反轉鏈表

#include <iostream> 
using namespace std; 
 
struct ListNode 

    int data; 
    struct ListNode *next; 
}; 
 
//創建鏈表 
void createList(ListNode *&Head) 

     int num = 0; 
     int flag = 0; 
     ListNode *p = NULL; 
     cin >> num; 
      
     Head = (ListNode *)malloc(sizeof(ListNode)); 
     while(num != 0) 
     { 
          if(flag == 0) 
          {   
               Head->data = num; 
               Head->next = NULL; 
               flag = 1; 
               p = Head; 
          } 
          else 
          { 
               ListNode *cur = (ListNode *)malloc(sizeof(ListNode)); 
               cur->data = num; 
               cur->next = NULL; 
               
               p->next = cur; 
               p = cur; 
          }  
          cin >> num; 
     } 

 
//打印鏈表 
void printList(ListNode *Head) 

     if(Head == NULL) 
     { 
          cout << "Head empty"<<endl; 
          return ; 
     } 
     ListNode *p = Head; 
     while(p != NULL) 
     { 
          cout << p->data <<" "; 
          p = p->next; 
     } 

 
//遞歸反轉鏈表(關鍵代碼)
ListNode* reverseLinkList_recursion(ListNode* pNode,ListNode*& head) 

     if(pNode == NULL || pNode->next == NULL) 
    { 
          head->next = NULL;    //把反轉后的最后一個節點的next域置為NULL 
          head = pNode; 
          return pNode; 
     } 
     ListNode* tmpNode = reverseLinkList_recursion(pNode->next,head);//返回原鏈表中pNode的下一個節點 
     tmpNode->next = pNode; 
     return pNode; 

void main() 

     ListNode *List = NULL; 
     cout << "創建鏈表:"; 
     createList(List); 
     cout << "鏈表元素:"; 
     printList(List); 
     reverseLinkList_recursion(List,List); 
     cout <<endl<< "倒序后:"; 
     printList(List); 

————————————————
 
本文已影響
相關文章
大亨pk10计划苹果版