[剑指offer]3_逆序打印链表

从今天开始要和大家分享打卡面试必刷算法题——剑指offer，希望能和大家一起进步！

1，题目描述

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

2，解题思路

方法一:采用栈。先进后出，可以实现顺序反转;
方法二:采用ArrayList的反转方法reverse()，实现顺序反转;
方法三:利用ArrayList的插入方法，每次都往index为0的位置插入，那么新插入的元素就会把后插入的元素默认往后移;
方法四:非递归。用一个while循环来做;
方法五:递归。

3，程序代码

/**
** 方法一
** 栈实现
*/
public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> list=new ArrayList<>();
    Stack<Integer> stack=new Stack<Integer>();
    //入栈
    while(listNode!=null){
        stack.add(listNode.val);
        listNode=listNode.next;
    }
    //取栈顶元素
    while(!stack.isEmpty()){
        list.add(stack.pop());
    }
    return list;
}

/**
** 方法二
** reverse逆序输出
*/
public static void printListFromTailToHead3() {
    ArrayList<Integer> list=new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    //反转方法
    Collections.reverse(list);
    System.out.println(list);
}

/**
** 方法三
** 利用ArrayList的插入方法，每次都往index为0的位置插入，那么新插入的元素就会把后插入的元素默认往后移
*/
    public static void printListFromTailToHead4() {
        ArrayList<Integer> list=new ArrayList<>();
        list.add(0,1);
        list.add(0,2);
        list.add(0,3);
        list.add(0,4);
        list.add(0,5);
        System.out.println(list);
    }

链表结点LinkNode如下；

package JianZhiOffer;

/**
 * @author 公众号:程序员的时光
 * @create 2020-09-22 15:03
 * @description
 */
public class ListNode {
    //链表结点的数据域
    public Integer val;
    //链表结点的指针域
    public ListNode next;

    //构造方法
    public ListNode(int val, ListNode next) {
        super();
        this.val = val;
        this.next = next;
    }
}

采用递归和非递归两种方式都能实现

package JianZhiOffer;

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

/**
 * @author 公众号:程序员的时光
 * @create 2020-09-22 14:50
 * @description
 */
public class No3_PrintList {
    //递归输出
    public static ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<>();
        if(listNode!=null){
            list=printListFromTailToHead1(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }
    //非递归输出
    public static ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<>();
        ListNode tmp=listNode;
        while(tmp!=null){
            list.add(0,tmp.val);
            tmp=tmp.next;
        }
        return list;
    }
    public static void main(String[] args) {
        ArrayList list=new ArrayList();
        ListNode head=new ListNode(0,null);
        ListNode PNode=head;

        for(int i=1; i<10; i++){
            ListNode node=new ListNode(i,null);
            PNode.next=node;
            PNode=node;
        }
        System.out.println(printListFromTailToHead1(head));
        System.out.println(printListFromTailToHead2(head));
    }
}

结果：

4，闲聊

源代码已经上传至码云：

[]: https://gitee.com/Huke-123/offer66_interview_questions/

欢迎大家关注我的B站账号：https://space.bilibili.com/92317221，后续我会采用视频的方式简单讲解；

好了，今天就先分享到这里了，下期继续给大家带来剑指offer面试题后续内容！更多干货、优质文章，欢迎关注我的原创技术公众号~