前言继续今天的算法题：从头到尾打印链表链表在看今天的话题之前，我们先来了解一下链表。链表是物理存储单元上的一种无序无顺序的存储结构。由于不必按顺序存储，链表的插入和删除操作可以达到O(1)的复杂度。熟悉数组的人都知道，数组需要一个连续的内存空间来存储。链表不需要它，它使用指针将内存块串联起来。常见的链表结构有：单链表、双向链表和循环链表。（图片来自参考链接）单向链表的第一个节点为头节点，最后一个节点为尾节点。从图中可以看出：当一个结点不指向下一个结点，而是指向null，一个空地址时，那么这个结点就是链表的最后一个结点，即尾结点。当我们插入或删除节点时，只需要修改下一个节点，即修改next指针指向的地址，比如这样一个链表：a->next=b,b->next=c,c->next=danext节点是b，b的下一个节点是c...如果我们想直接在ab中插入一个节点p，由于链表的不连续性，我们只需要修改a的下一个到p，p的下一个是b就可以了。a->next=p,p->next=b,b->next=c,c->next=d通俗的说，插入的时候，修改两个节点的follower即可。因此，与数组的插入和删除操作不同，链表的插入和删除操作非常高效，不需要考虑空间连续性的问题，所以对应的时间复杂度为O(1)。但是反过来，如果要查询第n条数据是谁，这样就比较麻烦了。不像数组，因为内存是连续的，所以很容易知道n对应的数据。链表需要一个一个的查找，所以链表的随机访问效率不如数组，时间复杂度为O(n)。循环链表和单链表的区别在于，尾节点指针会指向头节点，形成一个环，这就是循环链表。双向链表如图所示。双向链表和单向链表的区别在于，每个节点不仅有下一个节点的地址，还有上一个节点的地址。这样做有什么好处？它可以提高特定情况下的效率。比如我要在某个节点B的前面插入数据，那么我需要从头开始寻找某个节点的下一个点到这个B的地址，然后插入数据。而双向链表可以直接知道节点B的前驱节点地址，大大提高了插入效率。链表的基础知识介绍到这里，再来看一道与链表相关的算法题。题目：从头到尾打印链表输入一个链表的头节点，返回从尾到头每个节点的值（以数组形式返回）。例1：输入：head=[1,3,2]输出：[2,3,1]限制：0<=链表长度<=10000解1题意很简单，就是一个链表，现在我们需要从尾部开始然后打印链表的数字。那么我们可以想到可以使用的递归算法。递归算法其实就是两步，先递归再递归。我们可以先传到链表的最后一位，也就是next->null为空的时候，然后开始归档数据，依次输出，也就是完成从末尾开始输出数字的需求。递归阶段：走到链表的末尾就是结束标志。归档阶段：从末尾开始逐层输出数字，先输出到ArrayList，再转为数组。不明白的可以看代码：classSolution{ArrayList
