转载地址：http://www.cppblog.com/humanchao/archive/2008/02/29/43446.html
刚刚有人考了我一道题，逆序输出单链表：
我是这样答的（下面的代码为伪代码，不能通过编译）：
{
assert(pList);
if (pList == NULL)
return ;
string str;
while (pList)
{
str = string( * pList) + str;
pList = pList -> next;
}
printf( " %s " , str.c_str());
}
后来他让我想一想还有没有更为简单的方法了，当时允许我上网，我用了几分钟到网上找了一下，没有找到更好的办法，如果先把链表逆序，再顺序输出时间复杂度更高。
我走出大楼以后，忽然想到，是递归呀，对是递归：
void printSList(slist * pList)
{
assert(pList);
if (pList == NULL)
return ;
if (pList -> next == NULL)
printf( " %s " , * pList);
else
{
printSList(pList -> next);
printf( " %s " , * pList);
}
}
哎，人生中机会就是一瞬之间，错过不知道下一次又是什么时候。但只要做了就会收获，会一次比一次做的好。吃饭去了...
FeedBack: # re: 单链表逆序输出 2008-02-29 12:47 raof01 先逆序再输出比递归高效。
N个节点，递归就存在N次函数调用，而先逆序再输出就2次调用（分两个函数写的话）——当然不包括调用其他函数。其他函数如print()调用次数是固定的。假设N巨大，还有可能出现栈问题，而先做逆序仅仅是指针的赋值循环。 回复 更多评论
# re: 单链表逆序输出 2008-02-29 13:00 dldwk @raof01
“先逆序再输出”是最直观的想法，我的第一段代码是另外一种思路。“先逆序再输出”的时间复杂度是O（N*2），但会破坏原链表本身的结构。三种解决办法各有优缺点，让我选，我会选择我的第一段代码，这种实现最为清晰易懂。 回复 更多评论
# re: 单链表逆序输出 2008-02-29 13:04 hyou lol那个链尾==null时不该打印呀 否则岂不末尾打印两次？
哈无论如何 都是慢慢进步咯 学习了 回复 更多评论
# re: 单链表逆序输出 2008-02-29 13:27 魔域私服 学习了```` 回复 更多评论
# re: 单链表逆序输出[未登录] 2008-02-29 14:40 santa 如果你是去面dev的话你这个回答人家会不满意的，如果数据量大，递归绝对挂掉。递归的效率会很低，因为要设计到许多系统栈操作，比起逆序要低效许多许多。 回复 更多评论
# re: 单链表逆序输出 2008-02-29 17:08 浪迹天涯 面试时 切记使用傻傻的方法
我觉得递归 可能是最先想到的
第一张方法也很巧妙 已经回答的很好了 回复 更多评论
# re: 单链表逆序输出 2008-02-29 18:01 humanchao @浪迹天涯
谢谢您的鼓励！ 回复 更多评论
# re: 单链表逆序输出 2008-02-29 18:27 comiunknown 先把这个单项链表按顺序把每个节点的值压到一个堆栈里面，读完后，然后从堆栈中把值依次读出来，算法复杂度只有O(n)。感觉这个题是考堆栈。 回复 更多评论
# re: 单链表逆序输出 2008-03-01 10:00 winsty 递归的效率很低的... 回复 更多评论
# re: 单链表逆序输出[未登录] 2008-04-18 23:43 christanxw 递归绝对是失败的做法。 回复 更多评论
# re: 单链表逆序输出 2008-09-26 17:50 oracle3 分配一个数组，把指针放到数组中，然后for倒着打印，应该最简单 回复 更多评论
# re: 单链表逆序输出 2010-10-16 17:14 QQ124045670 递归那个方法我还没学到，所以我使用了分配一个数组，把指针放到数组中，然后for倒着打印
Status display(LinkList &L)
{
printf("n---------------------------显示单链线性表----------------------n");
LinkList p;
int n[100];
int j=100;
p=L->next; //打印的时候应该从头结点的下一个结点开始打印,否则会出现乱码
printf("n单链表为:t");
if(p!=NULL)
{
for(;p!=NULL;--j)
{
n[j-1]=p->date; //j-1是因为100要存放头结点的位置
p=p->next;
}
for(;j<100;j++)
{
printf("%d",n[j]);
}
}
free(p);
return 1;
}//display 回复 更多评论
# re: 单链表逆序输出 2011-09-18 21:47 wmj @comiunknown
我也这么想的 回复 更多评论