从尾到头打印链表

题目描述

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
本题知识点： 链表

思路

方案1：
链表有节点，每个节点又指向下一个节点，题目要求从尾到头打印链表的值，那么“后进先出”的栈是可以做到的。有栈的思想，不妨也可以试用递归来实现。递归需要有一个终止条件，这个终止条件就是传进来的链表节点不是空，用图描述大概如下：
先调用fucn(1)，然后递归调用该方法，这样,func(2)，func(3)。。。依次入栈，到func(6)，符合递归终止条件，将返回值放入到ArrayList中，然后func(5)同样返回，直到完成。
参考代码

import java.util.ArrayList;

/**
 * <p>
 * Title: Solution3a
 * </p>
 * <p>
 * Description:使用递归方式
 * </p>
 * 
 * @author SunShuo
 * @date 2018年12月23日
 */
public class Solution3a {
	
	public static ArrayList<Integer> res = new ArrayList<Integer>();
	
	public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
		if(listNode != null) {
			printListFromTailToHead(listNode.next);
			res.add(listNode.val);
		}
        return res;
    }
	
	
	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(2);
		ListNode node3 = new ListNode(3);
		ListNode node4 = new ListNode(4);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		printListFromTailToHead(node1);
		for (int i = 0; i < res.size(); i++) {
			System.out.println(res.get(i));
		}
	}

}

/**
 * <p>Title: ListNode</p>  
 * <p>Description: 链表</p>  
 * @author SunShuo  
 * @date 2018年12月23日
 */
class ListNode {
	int val;
	ListNode next = null;
	ListNode(int val) {
		this.val = val;
	}
}

方案2
不使用递归，但是依然用栈。
参考代码

import java.util.ArrayList;
import java.util.Stack;

/**  
 * <p>Title: Solution3b</p>  
 * <p>Description: </p>  
 * @author SunShuo  
 * @date 2018年12月23日  
*/
public class Solution3b {

	private static ArrayList<Integer> res = new ArrayList<>();
	
	public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
		Stack<Integer> stack = new Stack<>();
		while(listNode != null) {
			stack.push(listNode.val);
			listNode = listNode.next;
		}
		while(!stack.isEmpty()) {
			res.add(stack.pop());
		}
        return res;
    }
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(2);
		ListNode node3 = new ListNode(3);
		ListNode node4 = new ListNode(4);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		printListFromTailToHead(node1);
		for (int i = 0; i < res.size(); i++) {
			System.out.println(res.get(i));
		}
	}

}
/**
 * <p>Title: ListNode</p>  
 * <p>Description: 链表</p>  
 * @author SunShuo  
 * @date 2018年12月23日
 */
class ListNode {
	int val;
	ListNode next = null;
	ListNode(int val) {
		this.val = val;
	}
}