从后往前输出链表

Jul 15, 2017 14:20 · 261 words · 1 minute read

题目 🔗

输入一个链表，从尾到头打印链表每个节点的值。

解题思路 🔗

输出链表的值可以采用遍历的方法。但是遍历是从头到尾，因此可以采用栈的方式，先进后出的方式；
递归在本质上就是一个栈结构，要实现反过来输出链表，在每次访问一个结点的时候，先递归输出他后面的结点，在输出该结点的本身

代码 🔗

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by haigeek on 2017/7/13.
 */
class ListNode{
    int val;
    ListNode next=null;
    ListNode(int val){
        this.val=val;
    }
}
//非递归的方式
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>list=new ArrayList<>();
        while (!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }
}
//递归的方式
public class Solution2{
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer>list=new ArrayList<>();
        if(listNode!=null){
            this.printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }
}

tips 🔗

了解java链表的一种定义方式

public class ListNode{
  int val;
  ListNode next=null;
  ListNode(int val){
    this.val=val;
  }
}

加深对递归的认识

剑指offer 数据结构