算法-从尾到头打印链表

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

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 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

递归函数基础

函数代码中调用自己时称为递归,该函数被称为递归函数。递归函数是一个很高效的 开发技巧,可以极大的简化代码提高开发效率。递归函数与循环类似,循环可以完成的 事情,...

733
来自专栏程序员叨叨叨

6.1 关系操作符(Comparison Operators)

在上一章中,我们已经介绍了Cg语言的基础数据类型(7种)、内置数据类型,以及数组、结构、接口等类型,本章将在此基础上讨论Cg中的表达式,表达式由操作符(oper...

462
来自专栏用户2442861的专栏

异或的应用 及剑指offer 面试 40 数组中只出现一次的数字

转载请注明出处:http://blog.csdn.net/ns_code/article/details/27568975

982
来自专栏武培轩的专栏

Leetcode#557. Reverse Words in a String III(反转字符串中的单词 III)

给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。

543
来自专栏IT可乐

Java数据结构和算法(十二)——2-3-4树

  通过前面的介绍,我们知道在二叉树中,每个节点只有一个数据项,最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点,就是多叉树。本篇博客我们将介...

3417
来自专栏Python专栏

【数据结构与算法】一起搞定面试中的二叉树题目(二)

1203
来自专栏猿人谷

A+B for Matrices 及 C++ transform的用法

题目大意:给定两个矩阵,矩阵的最大大小是M*N(小于等于10),矩阵元素的值的绝对值小于等于100,求矩阵相加后全0的行以及列数。 1 #include<io...

1839
来自专栏武培轩的专栏

剑指Offer-二叉树的下一个结点

题目描述 给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。 思路 分析二叉...

2465
来自专栏desperate633

LintCode 单词切分题目分析

给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。

662
来自专栏iOSDevLog

数据结构和算法

数据结构和算法是计算机科学中最重要的概念之一。如果您不熟悉计算机科学或编程,本文将为您提供有关数据结构和算法的概述。这也是Landscape系列的第二集。

1114

扫码关注云+社区