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

痛定思痛。 2022-05-17 06:13 75阅读 0赞

链表的定义：

链表是一种物理[存储单元][Link 1]上非连续、非顺序的[存储结构][Link 2]，[数据元素][Link 3]的逻辑顺序是通过链表中的[指针][Link 4]链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储[数据元素][Link 3]的数据域，另一个是存储下一个结点地址的[指针][Link 5]域。

ps：因此这里指的链表（单向链表）只能往后遍历，无法逆向遍历，因此需要双向链表，一个节点有三个部分，前节点地址，数据区，后节点地址。可以双向遍历了。

**用递归的方法，结束条件是递归到最后的 listNode****.next为空**

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

节点代码：

class ListNode {
    	int val;//节点值
    	ListNode next = null;//下一个节点地址
    
    	ListNode(int val) {//有参构造
    		this.val = val;
    	}
    }

程序关键之处是**ArrayList list = new ArrayList();****写在了递归体之外，因此每次递归体中list.add所添加的节点值都是添进同一个数组。**

注：因为每次操作的都是同一个**数组**，其实return语句只在最后一次有实际作用（用来给调用此函数的程序返回倒置后的list），并为最后一次方法体服务，最后一次之前的return没有实际作用（最多有结束本次递归的作用）。

**程序的操作过程，与一种行为特别的相似，就是当你的袜子是反面的时候，你得先深入袜子内，抓住底部，然后往外抽，袜子就正面了，不断递归的过程就是插入袜子的过程，每次递归体结束的过程就是慢慢抽出来的过程（因为每一次递归的结束意味着有一个节点装入了新的Arraylist）。袜子的底部就是最后一个节点。**

[Link 1]: https://baike.baidu.com/item/%E5%AD%98%E5%82%A8%E5%8D%95%E5%85%83
[Link 2]: https://baike.baidu.com/item/%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84
[Link 3]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0
[Link 4]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88
[Link 5]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88/2878304