題目06：從尾到頭打印鏈表
輸入一個(gè)鏈表冈涧，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值茂附。
思路
一. 棧
從頭遍歷鏈表，先訪問的后輸出督弓，后訪問的先輸出营曼，“后進(jìn)先出”，利用棧來實(shí)現(xiàn)
二. 遞歸
遞歸本質(zhì)上就是一個(gè)棧的結(jié)構(gòu)愚隧，可以利用遞歸來實(shí)現(xiàn)蒂阱。但是當(dāng)鏈表比較長的時(shí)候，遞歸會(huì)導(dǎo)致函數(shù)調(diào)用的層級(jí)很深狂塘，有可能會(huì)導(dǎo)致函數(shù)調(diào)用棧的溢出
代碼實(shí)現(xiàn)
import java.util.Stack;
public class _06 {
private static class ListNode {
private int val;
private ListNode next;
public ListNode(int value) {
this.val = value;
}
}
public static void printListInversely1(ListNode root) {//用棧
Stack<ListNode> stack = new Stack<>();
while (root != null) {
stack.push(root);
root = root.next;
}
ListNode tmp;
while (!stack.isEmpty()) {
tmp = stack.pop();
System.out.print(tmp.val + " ");
}
}
public static void printListInversely2(ListNode root) {//遞歸
if (root != null) {
printListInversely2(root.next);
System.out.print(root.val + " ");
}
}
public static void main(String[] args) {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
n1.next =n2;
n2.next =n3;
n3.next =n4;
n4.next =n5;
printListInversely1(n1);
System.out.println();
printListInversely2(n1);
}
}
輸出：
5 4 3 2 1
5 4 3 2 1
