首页 > 代码库 > 从尾到头打印链表
从尾到头打印链表
题目描述
输入描述:
输入为链表的表头
输出描述:
输出为需要打印的“新链表”的表头
分析：
链表是一种动态数据结构，是因为在创建链表时，无须知道链表的长度。当插入一个结点时，我们只需为新结点分配内存，然后调整指针的指向，来确保新结点被链接到链表当中。内存分配不是在创建链表时一次性完成的，而是每添加一个结点分配一次内存。由于没有闲置的内存，链表的空间效率比数组高。
由于链表中的内存不是一次性分配的，因而我们无法保证链表的内存和数组一样是连续的。所以如果想在链表中找到它的第 i 个结点，我们只能从头结点开始，沿着指向下一个结点的指针遍历链表，它的时间效率为o(n)。而数组，我们可以根据下标在o(1)时间内找到第 i 个元素。
针对本题的思路分析：
解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序，可输出的顺序是从尾到头。也就是说，第一个遍历到的结点最后一个输出，而最后一个遍历到的结点第一个输出。这就是典型的“后进先出”，我们可以用栈来实现这种顺序。每经过一个结点时，把该结点放到一个栈中。当遍历完整个链表之后，再从栈顶逐个输出结点的值，此时输出的结点顺序已经反转过来了。
既然想到了用栈来实现这个函数，而递归在本质上就是一个栈结构，于是很自然的想到了用递归实现。要实现反过来输出链表，我们每访问到一个结点的时候，先递归输出它们后面的结点，再输出该结点的自身，这样链表的输出结果就反过来了。
/*** 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<Integer> printListFromTailToHead(ListNode listNode) { if(listNode==null){ ArrayList list=new ArrayList(); return list; } Stack<Integer> stack=new Stack<Integer>(); while(listNode!=null){//将数据压入栈中 stack.push(listNode.val); listNode=listNode.next; } ArrayList<Integer> arr=new ArrayList<Integer>(); while(!stack.isEmpty()){ arr.add(stack.pop());//将栈中的数据弹出再添加到链表中 } return arr; }}注意：代码思路借助栈，遍历的时候入栈，由于数据结构中栈的特点是先进后出，所以遍历的过程中压栈，推栈，完了弹栈加到ArrayList中。有两个容易出错的地方：第一，第一次测试用例，{}返回[ ],null是null，而[ ]是new ArrayList（）但是没有数据。第二，遍历stack用的方法是！stack.isEmpty()方法，而不是for循环size遍历。
另一种方法：借助递归实现
/*** 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<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> list=new ArrayList<Integer>(); ListNode pNode=listNode;//定义一个类似于指针的pNode if(pNode!=null){ if(pNode.next!=null){ list=printListFromTailToHead(pNode.next);//递归 } list.add(pNode.val); } return list; }}
从尾到头打印链表