题目描述
输入应该链表的头节点 , 从尾到头反过来打印出每个节点的值。链表定义如下 :
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 }