首页 > 基础资料 博客日记
从尾到头打印链表
2025-06-05 17:39:07基础资料围观22次
文章从尾到头打印链表分享给大家,欢迎收藏Java资料网,专注分享技术知识
题目描述
输入一个链表的头节点,按链表从尾到头的顺序返回每个节点的值(用数组返回)。
如输入{1,2,3}的链表如下图:
返回一个数组为[3,2,1]
0 <= 链表长度 <= 10000
示例1
输入:
{1,2,3}
返回值:
[3,2,1]
示例2
输入:
{67,0,24,58}
返回值:
[58,24,0,67]
思路及解答
⾸先我们需要想⽤哪些解法可以解,⼤概有如下:
- 使⽤栈
- 使⽤递归调⽤
- 头插法
借助栈实现
先把元素⾥⾯的元素从头到尾遍历取出放在栈⾥⾯,然后再把栈的元素去出来放在ArraList ⾥⾯。主要利⽤了栈的先进后出的规则,这样就可以实现倒序的功能。Java 代码实现如下:
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack = new Stack<>();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> results = new ArrayList<>();
while (!stack.isEmpty()) {
results.add(stack.pop());
}
return results;
}
}
递归调⽤
前⾯我们能想到栈,那么我们何必⾃⼰实现呢?其实⽅法的调⽤过程,就是⼀个天然的栈调⽤的过程呀,只需要判断当前节点是不是为空,为空则不输出,不为空则递归下⼀个节点,对下⼀个节点处理之后,把结果使⽤ArrayList.addAll() 加到结果中,再把⾃身加到结果中即可:
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> results = new ArrayList<>();
if(listNode!=null){
// 对后⾯的元素进⾏处理
results.addAll(printListFromTailToHead(listNode.next));
// 最后添加⾃身
results.add(listNode.val);
}
return results;
}
}
头插法
遍历每⼀个节点,然后把它插⼊到头部,这样⼀直遍历到尾的时候,就相当于将整个链表都反转⼀遍了,然后再从头到尾遍历放到ArryList 即可。
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ListNode head = new ListNode(-1);
while(listNode!=null){
// 先把当前node的next保存起来
ListNode temp = listNode.next;
// 把当前节点的next指针指向head的下⼀个节点
listNode.next = head.next;
// 把head的next指向当前节点
head.next = listNode;
// 将遍历的指针指向了遍历的下⼀个元素
listNode = temp;
}
ArrayList<Integer> results = new ArrayList<>();
head = head.next;
// 遍历输出
while(head!=null){
results.add(head.val);
head = head.next;
}
return results;
}
}
文章来源:https://www.cnblogs.com/seven97-top/p/18894404
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
标签:
相关文章
最新发布
- 记一次诡异的线上异常赋值排查:代码没错,结果不对
- hot100之子串
- 剑指offer-1、⼆维数组中的查找
- 从尾到头打印链表
- 秒杀/高并发解决方案+落地实现 (技术栈: SpringBoot+Mysql + Redis +RabbitMQ +MyBatis-Plus +Maven + Linux + Jmeter ) -03
- @ModelAttribute、@RequestBody、@RequestParam、@PathVariable 注解对比
- Java 样板代码库 Lombok 使用详解
- wso2~自定义event-publisher
- 数组数量数据数量大 1000万黑名单用户 一百亿基础用户 查询检索思路
- Spring AI 1.0 正式发布,让 Java 再次伟大!