一、题目：从尾到头打印链表
题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。
到解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序，可输出的顺序却是从尾到头。也就是说第一个遍历到的结点最后一个输出，而最后一个遍历到的结点第一个输出。这就是典型的“后进先出”，我们可以用栈实现这种顺序。
二、解题思路
每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，此时输出的结点的顺序已经反转过来了。
三、解决问题
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 > )
{
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();
linkedList.Add();
linkedList.Add();
linkedList.Add();
linkedList.Add(); PrintTestPortal(linkedList.Head);
}
（3）只有一个节点的链表
// 只有一个节点的链表
static void PrintTest2()
{
Console.WriteLine("TestCase2:");
SingleLinkedList<int> linkedList = new SingleLinkedList<int>();
linkedList.Add(); PrintTestPortal(linkedList.Head);
}
（4）鲁棒性测试：NULL
// 空链表
static void PrintTest3()
{
Console.WriteLine("TestCase3:"); PrintTestPortal(null);
}
测试结果如下图所示：
