程序員面試題精選100題(31)-從尾到頭輸出鏈表

時間:2019-09-22 編輯:范文亭
程序員面試題精選100題(31)-從尾到頭輸出鏈表

題目:輸入一個鏈表的頭結點,從尾到頭反過來輸出每個結點的值。鏈表結點定義如下:

struct ListNode

{

      int       m_nKey;

      ListNode* m_pNext;

};

方法一:

看到這道題后,第一反應是從頭到尾輸出比較簡單。于是很自然地想到把鏈表中鏈接結點的指針反轉過來,改變鏈表的方向。然后就可以從頭到尾輸出了。

void PrintListReversingly(ListNode* pHead)
{
  ListNode* pReverseHead=NULL;
  ListNode* cursor=pHead;
  //翻轉鏈表
  while(cursor!=NULL)
  {
    ListNode* next=cursor->next;
if(NULL==pReverseHead){
cursor->m_pNext=NULL;
}else{
cursor->m_pNext=pReverseHead;
}
pReverseHead=cursor;
cursor=next;
  }
  cursor=pReverseHead;//指向翻轉后的鏈表的頭
  while(cursor!=NULL)
  {
    printf("%d ",cursor->m_nKey);
cursor=cursor->m_pNext;
  }
}

方法二:

接下來的想法是從頭到尾遍歷鏈表,每經過一個結點的時候,把該結點放到一個棧中。當遍歷完整個鏈表后,再從棧頂開始輸出結點的值,此時輸出的結點的順序已經反轉過來了。該方法需要維護一個額外的棧,實現起來比較麻煩。

void PrintListReversingly_Iteratively(ListNode* pHead)
{
std::stack<ListNode*> nodes;
ListNode* pNode=pHead;
while(pNode!=NULL)
{
 nodes.push(pNode);
 pNode=pNode->m_pNext;
}
while(!nodes.empty())
{
 pNode=nodes.top();
 printf("%d\t",pNode->m_nKey);
 nodes.pop();
}
}

方法三:

既然想到了棧來實現這個函數,而遞歸本質上就是一個棧結構。于是很自然的又想到了用遞歸來實現。要實現反過來輸出鏈表,我們每訪問到一個結點的時候,先遞歸輸出它后面的結點,再輸出該結點自身,這樣鏈表的輸出結果就反過來了。

基于這樣的思路,不難寫出如下代碼:

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

// Print a list from end to beginning

// Input: pListHead - the head of list

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

void PrintListReversely(ListNode* pListHead)

{

      if(pListHead != NULL)

      {

            // Print the next node first

            if (pListHead->m_pNext != NULL)

            {

                  PrintListReversely(pListHead->m_pNext);

            }

 

            // Print this node

            printf("%d", pListHead->m_nKey);

      }

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