算法-从尾到头打印链表

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

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

相关文章

来自专栏逆向技术

逆向知识十三讲,汇编中数组的表现形式,以及还原数组

            逆向知识十三讲,汇编中数组的表现形式,以及还原数组 讲解数组之前,要了解数组的特性 1.数据具有连续性 2.数据类型相同 比如:   i...

1837
来自专栏小詹同学

Leetcode打卡 | No.24 两两交换链表中的节点

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

674
来自专栏Android干货

浅谈Base64编码算法

2916
来自专栏数据结构与算法

洛谷P3327 [SDOI2015]约数个数和(莫比乌斯反演)

题目描述 设d(x)为x的约数个数,给定N、M,求 \sum^N_{i=1}\sum^M_{j=1}d(ij)∑i=1N​∑j=1M​d(ij) 输入输出格式 ...

2544
来自专栏Python

推导式详解

推导式的套路 除列表推导式和生成器表达式之外,其实还有字典推导式、集合推导式等等。 下面是一个以列表推导式为例的推导式详细格式,同样适用于其他推导式。 vari...

1879
来自专栏蜉蝣禅修之道

基于Huffman编码的压缩软件的Python实现

1474
来自专栏ml

c语言格式大整理

1、C语言中,非零值为真,真用1表示;零值为假,假用0表示。 2、转义字符参考: \a 蜂鸣,响铃  \b 回退:向后退一格 ...

2887
来自专栏拭心的安卓进阶之路

@SuppressWarning 使用及支持的参数

@SuppressWarning @SuppressWarning 是一个注解,它的作用是抑制编译时的警告,可以用于标记整个类、某个方法、某个属性或者某个参数,...

1876
来自专栏前端儿

表达式求值

ACM队的mdd想做一个计算器,但是,他要做的不仅仅是一计算一个A+B的计算器,他想实现随便输入一个表达式都能求出它的值的计算器,现在请你帮助他来实现这个计算器...

1002
来自专栏ACM算法日常

leetcode题解 | 78. 子集

这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

743

扫码关注云+社区