剑指Offer JZ6 从尾到头打印链表

Ahci / 2023-09-04 / 原文

题目链接

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

输入{1,2,3}, 返回一个数组为[3,2,1]

示例 1:

输入：
{1,2,3}
返回值：
[3,2,1]

示例 2:

输入：
{67,0,24,58}
返回值：
[58,24,0,67]

思路

创建一个数组, 遍历链表的同时将链表元素加入数组, 最后将数组反转并返回.
创建一个栈, 遍历链表的同时让链表元素入栈, 之后创建数组再将链表元素出栈即可.

代码实现

链表定义格式:

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*/

数组:

import java.util.*;
import java.util.ArrayList;

public class Solution {
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        while(listNode != null) {
            list.add(listNode.val);
            listNode = listNode.next;
        }
        Collections.reverse(list);
        return list;
    }
}

栈:

import java.util.*;
import java.util.ArrayList;

public class Solution {
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<Integer>();

        while(listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }

        ArrayList<Integer> list = new ArrayList<>();
        while(!stack.empty()) {
            list.add(stack.pop());
        }

        return list;
    }
}