剑指Offer面试题：4.从尾到头打印链表
一、题目：从尾到头打印链表
题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。
到解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序，可输出的顺序却是从尾到头。也就是说第一个遍历到的结点最后一个输出，而最后一个遍历到的结点第一个输出。这就是典型的“后进先出”，我们可以用栈实现这种顺序。
二、解题思路
每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，此时输出的结点的顺序已经反转过来了。
三、解决问题
3.1 代码实现
这里使用的是自定义实现的链表类，其节点定义如下：
public class Node<T> { // 数据域 public T Item { get; set; } // 指针域 public Node<T> Next { get; set; } public Node() { } public Node(T item) { this.Item = item; } }
这里的自定义的单链表的实现请参考：《数据结构基础温故-1.线性表（中）》
（1）基于栈的循环版本
public static void PrintListReversinglyIteratively(Node<int> head) { Stack<Node<int>> stackNodes = new Stack<Node<int>>(); Node<int> node = head; // 单链表元素依次入栈 while (node != null) { stackNodes.Push(node); node = node.Next; } // 栈中的单链表元素依次出栈 while (stackNodes.Count > 0) { Node<int> top = stackNodes.Pop(); Console.Write("{0}", top.Item); } }
（2）递归版本
public static void PrintListReversinglyRecursively(Node<int> head) { if (head != null) { if (head.Next != null) { PrintListReversinglyRecursively(head.Next); } Console.Write("{0}", head.Item); } }
两个版本的对比：上面的基于递归的代码看起来很简洁，但有个问题：当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出。显式用栈基于循环实现的代码的鲁棒性要好一些。
3.2 单元测试
（1）单元测试主入口
// 测试主入口 static void PrintTestPortal(Node<int> head) { Console.WriteLine("-------Begin--------"); NormalPrint(head); Console.WriteLine(); PrintListReversinglyIteratively(head); Console.WriteLine(); PrintListReversinglyRecursively(head); Console.WriteLine("\n-------End--------"); } // 辅助方法：正序打印链表 static void NormalPrint(Node<int> head) { Node<int> temp = head; while(temp != null) { Console.Write("{0}",temp.Item); temp = temp.Next; } }
在测试入口中，我们首先正序打印链表，然后使用循环版从尾到头打印链表，最后使用递归版从尾到头打印链表。
（2）正常的多元素链表
// 1->2->3->4->5 static void PrintTest1() { Console.WriteLine("TestCase1:"); SingleLinkedList<int> linkedList = new SingleLinkedList<int>(); linkedList.Add(1); linkedList.Add(2); linkedList.Add(3); linkedList.Add(4); linkedList.Add(5); PrintTestPortal(linkedList.Head); }
（3）只有一个节点的链表
// 只有一个节点的链表 static void PrintTest2() { Console.WriteLine("TestCase2:"); SingleLinkedList<int> linkedList = new SingleLinkedList<int>(); linkedList.Add(1); PrintTestPortal(linkedList.Head); }
（4）鲁棒性测试：NULL
// 空链表 static void PrintTest3() { Console.WriteLine("TestCase3:"); PrintTestPortal(null); }
测试结果如下图所示：
正文到此结束
