算法-从尾到头打印链表

题目: 输入一个链表,要求从尾到头打印该链表,链表结点定义如下:

struct ListNode
{
  int value;
  ListNode *next;
};

解题思路: 要求很好理解,比如一个链表是:

打印的结果是:6 5 4 3 2 1 1.相信大多数人看到这个要求后的第一反应是反转链表,再从头打印,但是这样一来,原始数据就改变了。 2.当然我们可以建立新的内存空间,然后拷贝原链表中的value,毕竟最后要打印的只是value,这样我们就有了一个和原链表的value一样的链表,然后再反转它,这样一来原始数据就不变了,但是这样的操作太过繁琐:遍历拷贝,反转,顺序打印,释放内存的一系列操作在空间和时间复杂度上都消耗较大。 3.既然上一种方法想到了建立新的链表的方式,那么何不建立一个其他的数据结构更简单的完成这件事—栈,这个任务的特点是先遍历到的后打印,我们只需要将先遍历到的结点中的value压入栈中,遍历结束后做出栈操作,这样一来步骤就简化了很多。 4.既然想到了是一种“先遍历后打印,后遍历先打印”的操作,那么可不可以不借助栈来实现这个方法——递归。递归的思想在合并两个排序的链表题目中就使用过,只不过在该题目中我们返回的是最后一次递归的结果,而在本文的题目我们需要打印每一次递归的返回值。

关于思路3和4都是可以的,具体使用哪一个可以根据实际情况来决定,如果链表很长,那么递归调用的层数就会很深,可能导致函数调用栈溢出,用思路3的鲁棒性会更好一些。

代码实现:

//借助栈
void PrintListReversingly_Iteratively(ListNode* pHead)
{
    std::stack<ListNode*> nodes;

    ListNode* pNode = pHead;
    while(pNode != NULL)
    {
        nodes.push(pNode);
        pNode = pNode->next;
    }

    while(!nodes.empty())
    {
        pNode = nodes.top();
        printf("%d\t", pNode->value);
        nodes.pop();
    }
}
//递归实现
void PrintListReversingly_Recursively(ListNode* pHead)
{
    if(pHead != NULL)
    {
        if (pHead->next != NULL)
        {
            PrintListReversingly_Recursively(pHead->next);
        }

        printf("%d\t", pHead->value);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 链表中倒数第k个结点 [剑指offer] 链表中倒数第k个结点

经典的双指针法。定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动,从第k步开始,第二个指针也开始从链表的头指针开始遍历,由于两个...

902
来自专栏猿人谷

struct 与 typedef struct

1. 基本解释   typedef为C语言的关键字,作用是为一种数据类型定义一个新名字。这里的数据类型包括内部数据类型(int,char等)和自定义的数据类型(...

1966
来自专栏赵俊的Java专栏

删除元素

821
来自专栏Phoenix的Android之旅

父类静态方法可以重写吗?

比较坑的一个问题是,子类能否重写父类的静态方法? 答案当然是可以的。但是重写之后会发生什么,是否调用子类静态方法会执行子类的逻辑,这才是坑所在的地方。

752
来自专栏程序员互动联盟

【编程基础】C++ Primer快速入门之七:运算符

一、表达式的定义 什么是表达式?表达式,是由数字、运算符、数字分组符号(括号)、自由变量和约束变量等以能求得数值的有意义排列方法所得的组合(1)。1 + 2是个...

3064
来自专栏技术沉淀

Python: collections模块实例透析Collections模块

1798
来自专栏Kevin-ZhangCG

[ Java学习基础 ] Java的继承与多态

2326
来自专栏老秦求学

位运算及其编程妙用

位操作符通常用来对操作数进行位级的操作运算。首先将运算符转换为位级,然后对操作数执行计算。可以在比特级执行诸如加法,减法,乘法等的数学运算以便更快地处理。

1723
来自专栏风口上的猪的文章

.NET面试题系列[11] - IEnumerable<T>的派生类

ICollection<T>继承IEnumerable<T>。在其基础上,增加了Add,Remove等方法,可以修改集合的内容。IEnumerable<T>的直...

842
来自专栏青玉伏案

窥探Swift之别样的枚举类型

  想必写过程序的童鞋对枚举类型并不陌生吧,使用枚举类型的好处是多多的,在这儿就不做过多的赘述了。Fundation框架和UIKit中的枚举更是数不胜数,枚举可...

1937

扫码关注云+社区