03从尾到头打印链表

题目描述

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

方法1. 递归

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> list = new ArrayList<>();
    if (listNode != null) {
        list.addAll(printListFromTailToHead(listNode.next));
        list.add(listNode.val);
    }
    return list;
}

方法2. 反转链表

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ListNode prev = null, curr = listNode;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    curr = prev;
    ArrayList<Integer> list = new ArrayList<>();
    while (curr != null) {
        list.add(curr.val);
        curr = curr.next;
    }
    return list;
}

方法3. 使用栈

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    Stack<Integer> stack = new Stack<>();
    ListNode curr = listNode;
    while (curr != null) {
        stack.push(curr.val);
        curr = curr.next;
    }
    ArrayList<Integer> list = new ArrayList<>();
    while (!stack.isEmpty()) {
        list.add(stack.pop());
    }
    return list;
}