剑指offer学习（Java）——面试题6：从尾到头打印链表

╰半夏微凉° 2022-05-22 10:14 137阅读 0赞

题目：输入一个链表的头节点，从尾到头反过来打印每个节点的值。

这种要反过来的第一时间肯定想到了用栈，想到了栈也就想到了递归。

牛客练习地址：[从尾到头打印链表][Link 1]

使用栈的话：

/**
    *    public class ListNode {
    *        int val;
    *        ListNode next = null;
    *
    *        ListNode(int val) {
    *            this.val = val;
    *        }
    *    }
    *
    */
    import java.util.ArrayList;
    import java.util.Stack;
    public class Solution {
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            Stack<Integer> stack = new Stack<>();
            ArrayList<Integer> result = new ArrayList<>();
            while(listNode != null){
                stack.push(listNode.val);
                listNode = listNode.next;
            }
            while(!stack.empty()){
                result.add(stack.pop());
            }
            return result;
        }
    }

使用递归的话：

/**
    *    public class ListNode {
    *        int val;
    *        ListNode next = null;
    *
    *        ListNode(int val) {
    *            this.val = val;
    *        }
    *    }
    *
    */
    import java.util.ArrayList;
    public class Solution {
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            ArrayList<Integer> result = new ArrayList<>();
            printOne(listNode, result);
            return result;
        }
    
        private void printOne(ListNode listNode, ArrayList result){
            if(listNode != null){
                if(listNode.next != null){
                    printOne(listNode.next, result);
                }
                result.add(listNode.val);
            }
        }
    }

[Link 1]: https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&tPage=1&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking