面試題4：從尾到頭打印鏈表

方法一：利用棧實現

C++代碼：

 #include "stdafx.h"  
#include <iostream>  
#include <stack>  
using namespace std; 
 
//鏈表中的結點類型  
struct ListNode 
{ 
    int m_nKey; 
    ListNode *m_pNext; 
}; 
 
//從尾到頭打印鏈表  
void PrintLinkedListReversely(ListNode *pHead) 
{ 
    stack<ListNode *> tempStack; 
     
    if (pHead != NULL) 
    { 
        ListNode *pCurrent = pHead; 
        ListNode *pStackNode = NULL; 
 
        while (pCurrent != NULL) 
        { 
            tempStack.push(pCurrent); 
            pCurrent = pCurrent->m_pNext; 
        } 
 
        while (!tempStack.empty()) 
        { 
            pStackNode = tempStack.top(); 
            cout << pStackNode->m_nKey << " "; 
            tempStack.pop(); 
        } 
 
        cout << endl; 
    } 
} 
#include "stdafx.h"
#include <iostream>
#include <stack>
using namespace std;

//鏈表中的結點類型
struct ListNode
{
 int m_nKey;
 ListNode *m_pNext;
};

//從尾到頭打印鏈表
void PrintLinkedListReversely(ListNode *pHead)
{
 stack<ListNode *> tempStack;
   
 if (pHead != NULL)
 {
  ListNode *pCurrent = pHead;
        ListNode *pStackNode = NULL;

  while (pCurrent != NULL)
  {
   tempStack.push(pCurrent);
   pCurrent = pCurrent->m_pNext;
  }

        while (!tempStack.empty())
        {
   pStackNode = tempStack.top();
   cout << pStackNode->m_nKey << " ";
   tempStack.pop();
        }

  cout << endl;
 }
}

 

方法二：遞歸實現

C++代碼：

 #include "stdafx.h"  
#include <iostream>  
#include <stack>  
using namespace std; 
 
//鏈表中的結點類型  
struct ListNode 
{ 
    int m_nKey; 
    ListNode *m_pNext; 
}; 
 
//從尾到頭打印鏈表  
void PrintLinkedListReversely(ListNode *pHead) 
{ 
    if (pHead != NULL) 
    { 
        if (pHead->m_pNext != NULL) 
        { 
            PrintLinkedListReversely(pHead->m_pNext); 
        } 
 
        cout << pHead->m_nKey << " "; 
    } 
} 
 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    bool isHeadNode = true; 
    ListNode *pHeadNode = NULL; 
    ListNode *pListNode = NULL; 
    ListNode *pCurrentTail = NULL; 
 
    while (1) 
    { 
        if (isHeadNode) 
        {           
            pHeadNode = new ListNode(); 
            cin >> pHeadNode->m_nKey; 
            pHeadNode->m_pNext = NULL; 
            pCurrentTail = pHeadNode; 
            isHeadNode = false; 
        } 
        else 
        { 
            pListNode = new ListNode(); 
            cin >> pListNode->m_nKey; 
            if (pListNode->m_nKey == -1) 
            { 
                break; 
            } 
            pListNode->m_pNext = NULL; 
            pCurrentTail->m_pNext = pListNode; 
            pCurrentTail = pListNode; 
        } 
    } 
 
    PrintLinkedListReversely(pHeadNode); 
 
    ListNode *pNode = pHeadNode; 
    ListNode *pNext = NULL; 
    while (pNode != NULL) 
    { 
        pNext = pNode->m_pNext; 
        delete pNode; 
        pNode = pNext; 
    }    
 
    system("pause"); 
    return 0; 
} 
#include "stdafx.h"
#include <iostream>
#include <stack>
using namespace std;

//鏈表中的結點類型
struct ListNode
{
 int m_nKey;
 ListNode *m_pNext;
};

//從尾到頭打印鏈表
void PrintLinkedListReversely(ListNode *pHead)
{
 if (pHead != NULL)
 {
  if (pHead->m_pNext != NULL)
  {
   PrintLinkedListReversely(pHead->m_pNext);
  }

  cout << pHead->m_nKey << " ";
 }
}

int _tmain(int argc, _TCHAR* argv[])
{
 bool isHeadNode = true;
 ListNode *pHeadNode = NULL;
 ListNode *pListNode = NULL;
 ListNode *pCurrentTail = NULL;

 while (1)
 {
  if (isHeadNode)
  {    
   pHeadNode = new ListNode();
   cin >> pHeadNode->m_nKey;
   pHeadNode->m_pNext = NULL;
   pCurrentTail = pHeadNode;
   isHeadNode = false;
  }
  else
  {
   pListNode = new ListNode();
   cin >> pListNode->m_nKey;
   if (pListNode->m_nKey == -1)
   {
    break;
   }
   pListNode->m_pNext = NULL;
   pCurrentTail->m_pNext = pListNode;
   pCurrentTail = pListNode;
  }
 }

 PrintLinkedListReversely(pHeadNode);

 ListNode *pNode = pHeadNode;
 ListNode *pNext = NULL;
 while (pNode != NULL)
 {
  pNext = pNode->m_pNext;
  delete pNode;
  pNode = pNext;
 }  

 system("pause");
 return 0;
}

基於遞歸的代碼很簡潔，但它存在缺點：當鏈表非常長的時候就會導致函數調用的層級很深，從而有可能導致棧溢出。顯然相比方法一用棧基於循環實現的代碼的魯棒性更好些。