本文共 2642 字，大约阅读时间需要 8 分钟。

目录

一、问题描述

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

二、代码实现

1、使用栈

利用栈先进后出的特性：先从左到右遍历单链表，将所有元素添加到栈中；再将栈中所有元素弹出依次添加到ArrayList中。

/***    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
   
     printListFromTailToHead1(ListNode listNode) {        if (listNode == null) {            return new ArrayList
    
     ();        }                Stack
     
       stack = new Stack<>();        ListNode cur = listNode;        while (cur != null) {            stack.push(cur);            cur = cur.next;        }                ArrayList
      
        result = new ArrayList<>();        while (!stack.isEmpty()) {            ListNode temp = stack.pop();            result.add(temp.val);        }                return result;    }}
      
     
    
   

2、采用头插法重新插入链表元素，将链表逆序（改动了输入的单链表）

先获取一个逆序后的单链表，再依次插入到ArrayList中。

import java.util.ArrayList;public class Solution {        public ArrayList
   
     printListFromTailToHead2(ListNode listNode) {        if (listNode == null) {            return new ArrayList
    
     ();        }                listNode = reverse1(listNode);                ArrayList
     
       result = new ArrayList<>();        ListNode cur = listNode;        while (cur != null) {            result.add(cur.val);            cur = cur.next;        }                return result;       }    //将输入的单链表改成逆序（采用头插法将单链表的所有元素重新插到新链表上）    public static ListNode reverse1(ListNode head) {        if (head == null || head.next == null) {            return head;        }                ListNode newHead = null;        while (head != null) {            ListNode temp = head;            head = head.next;                        temp.next = newHead;            newHead = temp;        }                return newHead;    }    }
     
    
   

3、直接递归获取逆序结果的写法（不改动输入的单链表）

采用递归的写法，直接将逆序结果添加到ArrayList中。

import java.util.ArrayList;import java.util.Stack;public class Solution {    static ArrayList
   
     result = null;    public ArrayList
    
      printListFromTailToHead(ListNode listNode) {        if(listNode == null) {            return new ArrayList
     
      ();        }                result = new ArrayList<>();    //避免存放两次的结果，由于这是个类变量，将reverse方法和result声明为非static也可以不这么写        reverse(listNode);        return result;    }    private static void reverse(ListNode head) {        if (head.next != null) {            reverse(head.next);        }        result.add(head.val);    //non-static variable result cannot be referenced from a static context    }    }
     
    
   

转载地址：http://cfnii.baihongyu.com/