Java 剑指offer JZ6 从尾到头打印链表

文章目录

• Java 剑指offer JZ6 从尾到头打印链表
• 一、题目描述
• 二、递归写法
• 三、栈方法

   使用Java的递归和栈解决从尾到头打印链表的问题

一、题目描述

  输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

  如输入{1,2,3}的链表如下图:

二、递归写法

  由于这个题目需要我们从后面向前面开始打印这个数组。那肯定无法直接遍历链表得到从尾到头的逆序结果。但我们可以对遍历的结点进行一个递归，递归是到达底层后才会往上回溯，所以我们先递归到这个链表的最后面，然后不断向前收集节点值加入到ArrayList数组中。
  具体做法：

 ●终止条件： 递归进入链表尾，即节点为空节点时（listNode = null）结束递归。
 ●返回值： 每次返回子问题之后的全部输出（return res;）。
 ●本级任务： 每级子任务递归地进入下一级，等下一级的子问题输出数组返回时，将自己的节点值添加在数组末尾（res.add(listNode.val);）。

import java.util.ArrayList;
public class Solution {//递归函数public void recursion(ListNode listNode, ArrayList res){ if(listNode != null){//先往链表深处遍历recursion(listNode.next, res); //再填充到数组就是逆序res.add(listNode.val); }}public ArrayList printListFromTailToHead(ListNode listNode) {ArrayList res = new ArrayList();  //新建一个动态数组，也是最后输出的结果recursion(listNode, res);  //调用递归函数return res;}
}

三、栈方法

  栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。栈是先进后出的，符合逆序的特点
  具体做法：

 ●step 1：我们可以顺序遍历链表，将链表的值正序填到到栈中（push(listNode.val)）。
 ●step 2：然后再依次弹出栈中的元素，加入到数组中，即可实现链表逆序。

import java.util.*;
public class Solution {public ArrayList printListFromTailToHead(ListNode listNode) {ArrayList res = new ArrayList();  //新建一个动态数组，也是最后输出的结果Stack s = new Stack();  //新建一个栈，用于先进后出实现逆序//正序输出链表到栈中while(listNode != null){ s.push(listNode.val);  // push()函数把项压入堆栈顶部listNode = listNode.next;}//输出栈中元素到数组中while(!s.isEmpty()) res.add(s.pop());  //将栈的顶端值加入到 res数组return res;}
}

注意
  读栈的顶端值加入到 res数组时要使用 pop()函数，不要用peek(),它们的区别在于：
 ●Object peek（ ）
  查看堆栈顶部的对象，但不从堆栈中移除它。
 ●Object pop（ ）
  移除堆栈顶部的对象，并作为此函数的值返回该对象。