【剑指Offer】6. 从尾到头打印链表
题目描述
从尾到头反过来打印出每个结点的值。
解题思路
使用递归
要逆序打印链表 1->2->3（3,2,1)，可以先逆序打印链表 2->3(3,2)，最后再打印第一个节点 1。而链表 2->3 可以看成一个新的链表，要逆序打印该链表可以继续使用求解函数，也就是在求解函数中调用自己，这就是递归函数。
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> rel = new ArrayList<>();
if(listNode != null) {
rel.addAll(printListFromTailToHead(listNode.next));
rel.add(listNode.val);
}
return rel;
}
}头插法
使用头插法可以得到一个逆序的链表。
头结点和第一个节点的区别：
- 头结点是在头插法中使用的一个额外节点，这个节点不存储值；
- 第一个节点就是链表的第一个真正存储值的节点。
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
// 头插法
ListNode head = new ListNode(-1);
while(listNode != null) {
ListNode temp = listNode.next;
listNode.next = head.next;
head.next = listNode;
listNode = temp;
}
// 返回值
ArrayList<Integer> re = new ArrayList<>();
head = head.next;
while(head != null) {
re.add(head.val);
head = head.next;
}
return re;
}
}使用栈
栈具有后进先出的特点，在遍历链表时将值按顺序放入栈中，最后出栈的顺序即为逆序。
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.*;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack = new Stack<>();
while(listNode != null) {
stack.add(listNode.val);
listNode = listNode.next;
}
// 返回值
ArrayList<Integer> re = new ArrayList<>();
while(!stack.isEmpty()) {
re.add(stack.pop());
}
return re;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/08/05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
