《剑指offer》之从尾到头打印链表

前言

今天刷的一道题目，是关于链表的。

题目

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

分析

仅仅看这个题目，有点不知道怎么下手的感觉，意思明白，但是怎么做呢？首先我们的准备一个链表，题目给了提示，我们创建一个ListNode 类，内容如下

public class ListNode {

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

这样就可以用来表示一个链表了，比如我们创建一个
1 3 5 8 的链表

ListNode listNode=new ListNode(1);
listNode.next=new ListNode(3);
listNode.next.next=new ListNode(5);
listNode.next.next.next=new ListNode(8);

好了，准备工作算是做好了，我们接下来看看题目，要将链表的元素从头到尾装到list 中，这里有两种思路。栈的后进先出原理，先将链表数据压入栈中，然后依次从栈中取出数据存入到list 中。还有一种就是使用递归的方法，找到链表的最后一个节点，依次向前，我这里采用的就是递归的方法。

解法

使用递归，我们使用递归的方法，找到链表中的最后一个元素，将其加入到list 中。

public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<>();
        if(listNode!=null){
            add(list,listNode);
        }
        return list;

    }
    public static void add(ArrayList<Integer> list,ListNode listNode){
    //如果没有后续节点就将元素加入到list 中，如果有就递归找后续节点
        if(listNode.next!=null){
            add(list,listNode.next);
        }
        list.add(listNode.val);
    }

源代码

package com.quellanan.algorithm.day2;

import java.util.ArrayList;

/**
 * @ClassName Solution
 * @Description DOTO
 * @Author zhulinfeng
 * @Date 2020/1/30 11:38
 * @Version 1.0
 */
public class Solution {

    public static void main(String[] args) {

        ListNode listNode=new ListNode(1);
        listNode.next=new ListNode(3);
        listNode.next.next=new ListNode(5);
        listNode.next.next.next=new ListNode(8);

        ArrayList<Integer> list=printListFromTailToHead(listNode);

        while(listNode.next!=null){
            System.out.print(listNode.val+"\t");
            listNode=listNode.next;
        }
        System.out.println(listNode.val);


        for(int i=0;i<list.size();i++){
            System.out.print(list.get(i)+"\t");
        }
    }

    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<>();
        if(listNode!=null){
            add(list,listNode);
        }
        return list;

    }
    public static void add(ArrayList<Integer> list,ListNode listNode){
        if(listNode.next!=null){
            add(list,listNode.next);
        }
        list.add(listNode.val);
    }
}

测试