从尾到头打印链表

简介:
题目:输入一个链表的头结点,从尾到头反过来打印出每个结点的值。

链表结点定义如下:

struct ListNode
{
    int  m_nKey;
    ListNode *m_pNext;
};

解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序,可输出的顺序却是从尾到头。也就是说第一个遍历到的结点最后一个输出,而最后一个遍历到得结点第一个输出。这就是典型的“后进先出”,可以用实现这种顺序。每经过一个结点的时候,把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始逐个输出结点的值,此时输出的结点的顺序已经反转过来了。

实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void  PrintListReverse(ListNode *pHead)
{
     std::stack<ListNode*> nodes;
 
     ListNode *pNode = pHead;
     while (pNode != NULL)
     {
         nodes.push(pNode);
         pNode = pNode->m_pNext;
     }
 
     while (!nodes.empty())
     {
         pNode = nodes.top();
         printf ( "%d\t"  , pNode->m_nValue);
         nodes.pop();
     }
}

 

递归在本质上就是一个栈结构,于是很自然地想到用递归来实现。要实现反过来输出链表,每访问到一个结点的时候,先递归输出它后面的结点,再输出该结点自身,这样链表的输出结构就反过来了。

实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void  PrintListReversely(ListNode* pListHead)
{
       if (pListHead != NULL)
       {
             // Print the next node first
             if  (pListHead->m_pNext != NULL)
             {
                   PrintListReversely(pListHead->m_pNext);
             }
 
             // Print this node
             printf ( "%d" , pListHead->m_nKey);
       }
}

 

 



本文转自夏雪冬日博客园博客,原文链接:http://www.cnblogs.com/heyonggang/p/3404192.html,如需转载请自行联系原作者

目录
相关文章
|
C语言 C++
【九章斩题录】从尾到头打印链表(JZ6)
【九章斩题录】从尾到头打印链表(JZ6)
53 0
|
6月前
|
存储 Java C语言
剑指offer(牛客)——从尾到头打印链表
剑指offer(牛客)——从尾到头打印链表
39 1
|
6月前
【一刷《剑指Offer》】面试题 5:从尾到头打印链表
【一刷《剑指Offer》】面试题 5:从尾到头打印链表
|
6月前
剑指Offer06.从尾到头打印链表
剑指Offer06.从尾到头打印链表
39 0
|
6月前
《剑指offer》——从尾到头打印链表
《剑指offer》——从尾到头打印链表
|
6月前
|
Java
每日一题《剑指offer》链表篇之从尾到头打印链表
每日一题《剑指offer》链表篇之从尾到头打印链表
73 0
每日一题《剑指offer》链表篇之从尾到头打印链表
|
6月前
剑指 Offer 06:从尾到头打印链表
剑指 Offer 06:从尾到头打印链表
31 0
|
6月前
|
C++
【剑指offer】-从尾到头打印链表-03/67
【剑指offer】-从尾到头打印链表-03/67
|
6月前
剑指Offer LeetCode 面试题06. 从尾到头打印链表
剑指Offer LeetCode 面试题06. 从尾到头打印链表
28 0
|
6月前
剑指Offer 面试题06. 从尾到头打印链表
剑指Offer 面试题06. 从尾到头打印链表
35 0