单向链表 面试题,该如何处理

单向链表 面试题
面试了一次：
有一个题：一个单向链表，遍历一次，逆序输出。
我的答案：1 先建立一个数组，然后顺序遍历链表一次，遍历过程中存数组，最后通过数组逆序输出。
          2 新建立一个链表---链表2，然后遍历旧的链表，前插到链表2，最后通过链表2顺序输出。

HR貌似不满意。面试后思量了一下，是不是说要直接把链表反转？那不简单！反正没明白啥意思。难道真的可以遍历一遍就逆序输出链表中的东西？？？？

求简答。 单向链表?面试题 ?面试题 单向链表?
[解决办法]
全才的HR啊

引用:

面试了一次：
有一个题：一个单向链表，遍历一次，逆序输出。
我的答案：1 先建立一个数组，然后顺序遍历链表一次，遍历过程中存数组，最后通过数组逆序输出。
          2 新建立一个链表---链表2，然后遍历旧的链表，前插到链表2，最后通过链表2顺序输出。

HR貌似不满意。面试后思量了一下，是不是说要直接把链表反转？那不简单！反正没明白啥意思。难道真的可以遍历一遍就逆序输出链表中的东西？？？？

求简答。

[解决办法]
插入排序吗？
[解决办法]
入栈，你的方法都不算错，问题是你应该问HR有什么其他方面的要求，比如空间上，等等。
或者HR是背答案来面试的，如果你的答案不是他背过的，那么你就悲剧了。
[解决办法]
莫非是想说用前插法，然后直接遍历输出？？？
[解决办法]

pHead->next = NULL;
pNode p1 = pHead;
pNode p2 = p1->next;
pNpde p3 = p2->next;
while(p3)
{
    p2->next = p1;
    p1 = p2;
    p2 = p3;
    p3 = p3->next;
}
p2->next = p1;
pHead = p2;

[解决办法]
如果是直接使链表反向，那么下次输出的时候还要遍历一次，岂不是不满足只准遍历一次链表的要求了
[解决办法]
用递归
[解决办法]

引用:

用递归

很强大。
我建议是使用栈。

查看更多 下一篇