剑指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 }