从尾到头打印链表

发表于 | 分类于

题目06：从尾到头打印链表

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

思路

一. 栈

从头遍历链表，先访问的后输出，后访问的先输出，“后进先出”，利用栈来实现

二. 递归

递归本质上就是一个栈的结构，可以利用递归来实现。但是当链表比较长的时候，递归会导致函数调用的层级很深，有可能会导致函数调用栈的溢出

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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);
    }
}

输出：

1
2
5 4 3 2 1 
5 4 3 2 1
> >