剑指Offer从尾到头打印链表

题目：输入一个链表的头节点，从尾到头打印出每一个节点的值。(要求不改变链表的结构)

链表节点定义如下：

1 struct ListNode
2 {
3     int nKey;
4     ListNode *pNext;
5 }

思路一：由从尾到头容易想到栈的后进先出的性质，于是可以用栈实现。(如果可以改变链表的结构，则可以先把链表反转，再从头依次输出结果)

反转链表可参考：http://www.cnblogs.com/ivorfeng/archive/2013/05/02/3055471.html

code:

 1 //利用栈实现
 2 void PrintListInStack(ListNode *pHead)
 3 {
 4     ListNode *pCur = pHead;
 5     std::stack<ListNode*> stackA;
 6 
 7     while(pCur != NULL)
 8     {
 9         stackA.push(pCur);
10         pCur = pCur->pNext;
11     }
12 
13     while(!stackA.empty())
14     {
15         ListNode *pNode = stackA.top();
16         stackA.pop();
17         printf("%d ",pNode->nKey);
18     }
19 }

思路二：上面用到栈的性质，而递归的本质就是使用栈的，于是可以利用递归来实现。

code:

 1 //递归
 2 void PrintListRecurively(ListNode *pHead)
 3 {
 4     
 5     if(pHead != NULL)
 6     {
 7         PrintListRecurively(pHead->pNext);
 8         printf("%d ", pHead->nKey);
 9     }
10 }

下面是main函数和一些建立函数：

 1 //建立链表
 2 void buildList(ListNode *& pHead)
 3 {
 4     int tmp;
 5     ListNode *pPre= NULL;
 6     printf("建立链表,以0表示终止:\n");
 7     while(scanf("%d", &tmp) && tmp != 0)
 8     {
 9         ListNode *p = new ListNode();
10         p->nKey = tmp;
11         p->pNext = NULL;
12         if(pHead == NULL)
13         {
14             pHead = p;
15             pPre = pHead;
16         }
17         else
18         {
19             pPre->pNext = p;
20             pPre = pPre->pNext;
21         }
22     }
23 }
24 //顺序输出链表
25 void PrintListInOrder(ListNode *pHead)
26 {
27     ListNode *pCur = pHead;
28     printf("链表顺序输出:\n");
29     while(pCur!= NULL)
30     {
31         printf("%d ",pCur->nKey);
32         pCur = pCur->pNext;
33     }
34     printf("\n");
35 }
36 
37 int main()
38 {
39     ListNode *pHead = NULL;
40     buildList(pHead);
41     PrintListInOrder(pHead);
42     printf("链表逆序输出:\n");
43     PrintListRecurively(pHead);
44     return 0;
45 }

example: