【剑指offer】面试题6：从尾到头打印链表

川长思鸟来 2022-04-01 14:29 139阅读 0赞

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

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

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

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

*  **栈实现代码**

public class PrintFromTailToStart {
    
    	static class Node{
    		public int data;
    		public Node next;
    		
    		public Node(){
    			
    		}
    		
    		public Node(int data){
    			this.data = data;
    		}
    	}
    	
    	/**
    	 * 栈结构实现：先进后出
    	 */
    	public static void printFromTailToStart(Node node){
    		
    		if(node == null){
    			System.out.println("输入的链表为空！");
    			return;
    		}
    		
    		// 创建一个Node型的栈结构
    		Stack<Node> stack = new Stack<Node>();
    		while(node != null){
    			stack.push(node);   // 将node节点压入栈中
    			node = node.next;   // 遍历链表
    		}
    		// 打印栈中元素
    		while(!stack.isEmpty()){
    			System.out.println(stack.pop().data);
    		}
    	}
    	
    	/**
    	 * 测试
    	 */
    	public static void main(String[] args) {
    		Node start = new Node(1);
    		Node second = new Node(2);
    		Node third = new Node(3);
    		start.next = second;
    		second.next = third;
    		
    		printFromTailToStart(start);
    	}
    }

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

*  **递归实现代码**

public class PrintFromTailToStart {
    
    	static class Node{
    		public int data;
    		public Node next;
    		
    		public Node(){
    			
    		}
    		
    		public Node(int data){
    			this.data = data;
    		}
    	}
    	
    	/**
    	 * 递归实现
    	 */
    	public static void printTailToStartRec(Node node) {
    		if(node != null){
    			// 递归终止条件：node的后继节点为空
    			if(node.next != null){
    				printTailToStartRec(node.next);  // 递归
    			}
    			System.out.println(node.data);
    		}else{
    			System.out.println("输入的链表为空！");
    		}
    	}
    	
    	/**
    	 * 测试
    	 */
    	public static void main(String[] args) {
    		Node start = new Node(1);
    		Node second = new Node(2);
    		Node third = new Node(3);
    		start.next = second;
    		second.next = third;
    		
    		printTailToStartRec(start);
    	}
    }

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