从尾到头打印链表

略

题目：输入一个链表，从尾到头打印链表每个节点的值。

分析

  链表是一种动态的数据结构，创建链表时，无须知道链表的长度。当插入一个结点时，只需要为新的结点分配内存。然后调整指针的指向来确保新结点被链接到链表当中。题目中要求要从尾到头打印链表的每个结点的值，自然想到要去遍历链表，但是遍历的顺序是从头到尾的，可输出是从尾到头，由这可以想到用栈去实现这个顺序。遍历链表时，依次把结点值放到栈中，最后再从栈顶开始输出结点的值。

  是否可以用其他的方法呢？答案是可以的，这里还可以用到一个递归的方法。要想打印这个结点，必须先打印该结点后面的一个结点。

代码实现

使用栈

代码如下：

/**
*    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) {
        Stack<Integer> stack=new Stack<Integer>();//栈
        while(listNode!=null){//遍历链表，把结点值依次放到栈中
            stack.push(listNode.val);
            listNode=listNode.next;     
        }
        
        ArrayList<Integer> list=new ArrayList<Integer>();
        while(!stack.isEmpty()){
            list.add(stack.pop());//出栈，结点值依次放到list中
        }
        return list;
    }
}

使用递归

代码如下：

/**
*    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;
        if(pNode!=null){
            if(pNode.next!=null){
                list=printListFromTailToHead(pNode.next);//使用递归来实现
            }
            list.add(pNode.val);
        }
        
        return list;
    }
}

总结

合理运用栈的机制，可以很容易的实现反转字符串.