剑指Offer名企面试题5：从尾到头打印链表（Java实现）

曾经终败给现在 2021-12-16 22:11 134阅读 0赞

这个题目是从尾到头打印链表，我们前面介绍过利用栈来反转链表和利用两个指针调转链表next关系来反转链表，这里是从尾到头打印链表，不涉及链表结构的改变，我们只是遍历链表的时候，打印是从尾部开始。

剑指Offer上面的一个给出了两个思路，一个是用栈来实现，这个就不说了。另一个是用递归来实现，递归在本质上是一种特殊的栈结构，要实现反过来输出链表，我们每访问一个节点的时候，先递归输出他后面的节点，再输出该节点自身。这样链表就可以从尾到头打印了。

关键代码如下：

![20190706094145986.png][]

思路很简单，实现起来也很简单，就是递归让人难以理解。

这里给出一个完整的示例：

package com.xxx.algorithm;
    
    public class Question_5 {
    
    	public static class Node{
    		String val;
    		public Node(String val){
    			this.val = val;
    		}
    		Node next;
    		
    		@Override
    		public String toString(){
    			return "Node("+val+")";
    		}
    	}
    	
    	public static class LinkedList{
    		Node head;
    		public void insert(String val){
    			if(head==null){
    				head = new Node(val);
    			}else{
    				Node cur = head;
    				while(cur.next!=null){
    					cur = cur.next;
    				}
    				cur.next = new Node(val);
    			}
    		}
    		
    		public void display(){
    			if(head==null)return;
    			System.out.print("list:");
    			Node cur = head;
    			while(cur!=null){
    				System.out.print(cur+"->");
    				cur = cur.next;
    			}
    			System.out.print("null");
    			System.out.println();
    		}
    		
    		public void tail2Head(Node headNode){
    			if(headNode!=null){
    				if(headNode.next!=null){
    					tail2Head(headNode.next);
    				}
    				System.out.print(headNode+"->");
    			}
    		}
    	}
    	
    	public static void main(String[] args) {
    		LinkedList list = new LinkedList();
    		list.insert("a");
    		list.insert("b");
    		list.insert("c");
    		list.insert("d");
    		list.insert("e");
    		list.insert("f");
    		list.insert("g");
    		System.out.println("原始链表：");
    		list.display();
    		System.out.println("从尾到头打印：");
    		list.tail2Head(list.head);
    	}
    
    }

运行程序，打印信息如下：

原始链表：
    list:Node(a)->Node(b)->Node(c)->Node(d)->Node(e)->Node(f)->Node(g)->null
    从尾到头打印：
    Node(g)->Node(f)->Node(e)->Node(d)->Node(c)->Node(b)->Node(a)->

[20190706094145986.png]: /images/20211214/fbaccb05ec80464a95379f923a8ce266.png