剑指Offer面试题5（Java版）：从尾到头打印链表

忘是亡心i 2022-07-16 04:53 145阅读 0赞

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

看到这道题，很多人的第一反应是从头到尾输出将会比较简单，于是我们很自然的想到把链表中的节点的指针反转过来，改变链表的方向，然后就可以从头到尾输出了。但该方法改变原来链表的结构。是否允许在打印链表的时候修改链表的结构？这个取决于面试官的要求，因此在面试的时候我们要询问清楚面试官的要求。

通常打印是一个只读操作，我们不希望打印时修改内容。假设面试官也要求这个题目不能改变链表的结构。

接下来我们想到解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序，可输出的顺序却是从尾到头。也就是说第一个遍历的节点最后一个输出，而最后一个遍历到的节点第一个输出。这就是典型的'后进先出“，我们可以从栈实现这种顺序。没经过一个节点的时候，把该节点放到一个栈中。当遍历完整的链表后，再从栈顶开始逐个输出节点的值，此时输出的节点的顺序已经反转过来了。

既然想到了用栈来实现这个函数，而递归在本身上就是一个栈结构，于是自然就想到了用递归来实现。要实现反过来输出链表，我们没访问到一个节点的时候，先递归输出后面的 节点，再输出该节点本身，这样链表的输出结果就反过来了。

实现代码如下：

**\[html\]**  [view plain][]   [copy][view plain]

1.  **<****pre** name="code" class="java"**>**package offer;  
2.    
3.  import java.util.Stack;  
4.    
5.  class Node \{  
6.      public int data;  
7.      public Node nextNode;  
8.    
9.      public Node() \{  
10.   
11.     \}  
12.   
13.     public Node(int data) \{  
14.         this.data = data;  
15.     \}  
16. \}  
17.   
18. public class E05FromTailToStart \{  
19.   
20.     public static void main(String\[\] args) \{  
21.         Node start = new Node(1);  
22.         Node two = new Node(2);  
23.         start.nextNode = two;  
24.           
25.         // Node two = new Node(2);  
26.         // start.nextNode = two;  
27.         printTailToStartRec(start);  
28.         printTailToStartStack(start);  
29.   
30.     \}  
31.   
32.     // 采用递归调用的方法  
33.     private static void printTailToStartRec(Node start) \{  
34.         if (start != null) \{  
35.             if (start.nextNode != null) \{  
36.                 printTailToStartRec(start.nextNode);  
37.             \}  
38.             System.out.println(start.data);  
39.         \}  
40.         else\{  
41.             System.out.println("list is null!");  
42.         \}  
43.     \}  
44.   
45.     // 采用栈--先进后出的方法  
46.     private static void printTailToStartStack(Node node) \{  
47.         if (node == null) \{  
48.             System.out.println("list is null");  
49.             return;  
50.         \}  
51.   
52.         Stack**<****Node****>** stack = new Stack**<****Node****>**();  
53.         while (node != null) \{  
54.             stack.push(node);  
55.             node = node.nextNode;  
56.         \}  
57.         while (!stack.isEmpty()) \{  
58.             System.out.println(stack.pop().data);  
59.         \}  
60.   
61.     \}  
62. \}

上面的基于递归的代码看起来很简洁，但有个问题：当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出。显式用栈基于循环的代码的鲁棒性要好一些。

[view plain]: http://blog.csdn.net/jsqfengbao/article/details/47053189#