剑指offer换空格教程（剑指offer-从尾到头打印单向链表）

链表结构如下：

class ListNode { int value ; ListNode next; public ListNode(int value) { this.value = value; } public ListNode(int value, ListNode next) { this.value = value; this.next = next; } }

解题过程：

1.看到这道题第一反应从头到尾打印链表遍历一遍链表就可以。那么从尾到头打印，势必要用栈结构实现，栈的特点先进后出。所以我们用一个辅助的栈来实现。代码如下

/** * 基于辅助空间数据结构实现 */ public static void printLinkedList(ListNode listNode) { if (listNode == null) { return; } Stack<ListNode> listNodeStack = new Stack<>(); while (listNode != null) { listNodeStack.push(listNode); listNode = listNode.next; } ListNode tmpNode; while (!listNodeStack.empty()) { tmpNode = listNodeStack.pop(); System.out.print(tmpNode.value " "); } }

2.函数调用也有一个特点，函数存放结构也是一个栈结构。

比如A函数调用B函数，B函数调用C函数，那么在栈中存储的顺序就是ABC，调用顺序就是C先调用，返回结果B调用，返回A最后调用。所以我们可以基于栈进行实现。

/** * 基于函数调用自身的栈属性实现 * @param listNode */ public static void printLinkedList1(ListNode listNode) { if (listNode == null) { return; } printLinkedList1(listNode.next); System.out.print(listNode.value " "); }

3.测试用例：

public static void main(String[] args) { ListNode node5 = new ListNode(5, null); ListNode node4 = new ListNode(4, node5); ListNode node3 = new ListNode(3, node4); ListNode node2 = new ListNode(2, node3); ListNode node1 = new ListNode(1, node2); printLinkedList(node1); System.out.println(); printLinkedList1(node1); }

结果：

,