【面试题3-从尾到头打印链表】

剑指offer第三题。

题目描述

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

解题思路

这一题给一个单向链表，然后你反向打印出来。其实最容易想到的就是两个方案，一个是将这个链表进行反置，然后依次打印即可。一个就是通过栈这个数据结构，先进后出，那么也可以反向打印出来。由于用栈比较简单，但是链表的反置稍微难一点并且重要，所以本文用反置链表的方式解决。

我的答案

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        
        if(listNode == null){
            return res;
        }
        
        ListNode pre = null;
        ListNode curr = listNode;
        while(curr != null){
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        //pre就是反向链表的头结点
        while(pre != null){
            res.add(pre.val);
            pre = pre.next;
        }
        
        return res;
    }
}