/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */ import java.util.ArrayList; public class Solution { /** * 输⼊⼀个链表,按链表从尾到头的顺序返回⼀个ArrayList。 * 方式一:借助栈 * 方式二:递归调用 * 方式三:头插法 * */ /*方式一:借助栈*/ public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { Stack<Integer> stack = new Stack<>(); while (listNode!=null){ stack.push(listNode.val); listNode = listNode.next; } ArrayList<Integer> result = new ArrayList<>(); while (!stack.isEmpty()){ result.add(stack.pop()); } return result; } /*方式二:递归调用*/ public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) { ArrayList<Integer> results = new ArrayList<>(); if(listNode != null){ results.addAll(printListFromTailToHead2(listNode.next)); results.add(listNode.val); } return results; } /*方式三:头插法*/ public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) { ListNode head = new ListNode(-1); while (listNode !=null) { // 先把当前node的next保存起来 ListNode temp = listNode.next; // 把当前节点的next指针指向head的下⼀个节点 listNode.next = head.next; // 把head的next指向当前节点--头插法,只在头部处理next节点处理 head.next=listNode; // 将遍历的指针指向了遍历的下⼀个元素 listNode = temp; } // 遍历获取节点 ArrayList<Integer> results = new ArrayList<>(); head = head.next; while(head!=null){ results.add(head.val); head = head.next; } return results; } }