【算法怎么就这么难——挑战剑指offer】系列03:逆序打印单链表

本系列的算法原题来自于“牛客网-剑指offer”,写这个板块,不仅仅是解决算法问题本身,更是手动提高难度、自行变式,思考更多的解决方案,以带给自己一些启发。

1. 【逆序打印单链表】原始题目

算法原题链接:https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&tPage=1&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

原题目描述:

输入一个单链表,按链表值从尾到头的顺序返回一个ArrayList。

单链表的简单设计

1
2
3
4
5
6
7
8
class ListNode {
    int val;
    ListNode next = null;
 
    ListNode(int val) {
        this.val = val;
    }
}

最先想到的办法:栈

其实jdk提供的工具类也可以做到

到此为止,原题目已经解答完毕。

但是,我们说这个系列不能仅仅局限于解决原始问题,更要手动加大难度,创造更多思路和方案。所以,接下来:

2. 加大原题难度:不允许使用额外的集合、工具​​​​​​​

递归存储

使用递归的方式虽然没有显式扩展额外空间,但在内存中创建了递归方法区(递归本来也是栈结构),所以仍然会比较消耗性能。

利用三指针进行原地翻转

发表评论