剑指offer-面试题6
程序员文章站
2022-07-14 20:24:32
...
1. 习题介绍
题目:
输入一个链表的头结点,从尾到头反过来打印出每个结点的值。
链表的结点定义如下:
public class ListNode {
int val;
ListNode next=null;
public ListNode(int val){
this.val = val;
}
public ListNode() {
}
}
第一思路:
我的第一思路是从头到尾输出类比数组那样,于是乎想把链表中的链表结点的指针反转过来,改变链表的方向,然后实现从头到尾输出(结果为从尾到头输出),可是发现修改链表的指针,反转链表的结构比较麻烦。于是乎放弃。(改变链表的方向也是需要遍历一次链表然后修改每个链表的指针域)
最优解思路:
借助于栈:我们从头到尾遍历链表,可以把遍历的结果放入栈中(先进后出),这样输出栈就实现了从尾到头输出链表元素。
public void printListFromTailToHead2(ListNode node){
// 如果链表为空,直接返回
if (node == null)
return;
// 借助于栈
Stack<ListNode> stack = new Stack<>();
// 把数据放入栈中
while (node != null) {
stack.push(node);
node = node.next;
}
// 出栈
while (!stack.isEmpty()) {
System.out.println(stack.pop().val+" ");
}
}
**借助于递归:**因为栈的本质就是一个递归,所以递归也可以实现链表倒着输出,即每访问到一个结点的时候,先递归输出它后面的结点,再输出该结点自身,这样链表的结果就反过来了。
public void printListFromTailToHead3(ListNode node){
// 当链表不为空
if(node!=null){
// 递归条件
if(node.next!=null){
printListFromTailToHead3(node.next);
}
System.out.print(node.val + " ");
}
}
**递归的小问题:**当链表非常长时,就会使递归的层级很深,从而有可能导致函数调用栈溢出。显示用栈基于循环实现代码的鲁棒性要好一些。
测试:
@Test
public void fun(){
ListNode listNode = new ListNode();
ListNode head=listNode;
for (int i=0;i<10;i++){
ListNode node = new ListNode(i);
head.next=node;
head=head.next;
}
printListFromTailToHead3(listNode.next);
}
2. 小结
考查队单项链表的理解和编程能力;
考查对循环、递归、栈的理解及应用。
参考资料:
上一篇: 六、一些函数使用
下一篇: Pytorch入坑指南
推荐阅读
-
剑指offer笔记面试题1----赋值运算符函数
-
剑指offer笔记面试题2----实现Singleton模式
-
剑指 offer代码最优解析——面试题35第一个只出现一次的字符
-
《剑指offer》面试题6 重建二叉树
-
剑指offer面试题49. 丑数
-
【剑指offer】面试题49. 丑数
-
剑指offer. 面试题49. 丑数. 动态规划解法
-
20200329-剑指offer-面试题48. 最长不含重复字符的子字符串(滑动窗口)
-
leetcode 160剑指offer面试题52. 两个链表的第一个公共节点(python3)
-
leetcode 面试题32 (剑指offer)- II. 从上到下打印二叉树 II(python3)