劍指Offer_6_從尾到頭列印連結清單

題目描述

       輸入應該連結清單的頭節點 , 從尾到頭反過來列印出每個節點的值。連結清單定義如下 :

1 typedef struct ListNode
2 {
3     int m_nKey ;
4     ListNode * m_pNext ;
5 }ListNode;      

　　分析：

　　　　可能有人的第一反應是将連結清單中的節點指針翻轉過來。但是改變原有的連結清單結構可能在某些情況下不被允許。

　　　　列印是一個隻讀操作，首先周遊一遍連結清單，但要做到逆序列印，可以用棧将節點裡面的值存起來。然後将棧push至空。

連結清單逆序列印代碼 ：

1 void PrintListNode(ListNode *pHead){
 2     stack<int> sk ;
 3     while(pHead !=NULL){
 4         sk.push(pHead->m_nKey);
 5         pHead = pHead->m_pNext ;
 6     }
 7     // 列印
 8     while(!sk.empty()){
 9         cout << sk.top()<<endl ;
10         sk.pop();
11     }
12 }      

完整代碼 :

此處連結清單 listNode 為舉例 執行個體化 為了 0->1->2->3->4->5->6->7->8->9->10->null ;  

1 #include<iostream>
 2 #include<malloc.h>
 3 #include<stack>
 4 
 5 using namespace std ;
 6 
 7 #define N 10
 8 
 9 typedef struct ListNode
10 {
11     int m_nKey ;
12     ListNode * m_pNext ;
13 }ListNode;
14 
15 void PrintListNode(ListNode *pHead){
16     stack<int> sk ;
17     while(pHead !=NULL){
18         sk.push(pHead->m_nKey);
19         pHead = pHead->m_pNext ;
20     }
21     // 列印
22     while(!sk.empty()){
23         cout << sk.top()<<endl ;
24         sk.pop();
25     }
26 }
27 int main(){
28     ListNode *pHead = (ListNode*)malloc(sizeof(ListNode*)) ;
29     ListNode *listNode = (ListNode*)malloc(sizeof(ListNode*)) ;
30     listNode->m_nKey = 0 ;
31     pHead = listNode ;
32     for(int i=0;i<N;i++){
33         ListNode *pNew = (ListNode*)malloc(sizeof(ListNode*))  ;
34         pNew->m_nKey = i+1 ;
35         listNode->m_pNext = pNew ;
36         listNode = listNode->m_pNext ;
37     }
38     listNode->m_pNext = NULL ;
39     PrintListNode(pHead);
40     return 0 ;
41 }      

  列印結果：

10
9
8
7
6
5
4
3
2
1
0

Process returned 0 (0x0)   execution time : 0.189 s
Press any key to continue.      

 此題除了使用棧，還可以使用遞歸。

代碼差别隻在PrintListNode函數。

1 #include<iostream>
 2 #include<malloc.h>
 3 #include<stack>
 4 
 5 using namespace std ;
 6 
 7 #define N 10
 8 
 9 typedef struct ListNode
10 {
11     int m_nKey ;
12     ListNode * m_pNext ;
13 }ListNode;
14 
15 void PrintListNode(ListNode *pHead){
16     if(pHead->m_pNext!=NULL){
17         PrintListNode(pHead->m_pNext);
18     }
19     cout << pHead->m_nKey << endl;
20 }
21 int main(){
22     ListNode *pHead = (ListNode*)malloc(sizeof(ListNode*)) ;
23     ListNode *listNode = (ListNode*)malloc(sizeof(ListNode*)) ;
24     listNode->m_nKey = 0 ;
25     pHead = listNode ;
26     for(int i=0;i<N;i++){
27         ListNode *pNew = (ListNode*)malloc(sizeof(ListNode*))  ;
28         pNew->m_nKey = i+1 ;
29         listNode->m_pNext = pNew ;
30         listNode = listNode->m_pNext ;
31     }
32     listNode->m_pNext = NULL ;
33     PrintListNode(pHead);
34     return 0 ;
35 }