剑指Offer - 九度1511 - 从尾到头打印链表

剑指Offer - 九度1511 - 从尾到头打印链表
2013-11-29 21:08

题目描述：: 输入一个链表，从尾到头打印链表每个节点的值。

输入：: 每个输入文件仅包含一组测试样例。
每一组测试案例包含多行，每行一个大于0的整数，代表一个链表的节点。第一行是链表第一个节点的值，依次类推。当输入到-1时代表链表输入完毕。-1本身不属于链表。

输出：: 对应每个测试案例，以从尾到头的顺序输出链表每个节点的值，每个值占一行。

样例输入：

样例输出：

题意分析：
　　给定一条单链表，从未到头打印出来。第一个念头是可以用头递归的写法进行倒序输出，但不论头递归还是尾递归都不是个会写代码的人该写出来的，因为递归调用中的栈操作开销太累，而且百万级的数据就能搞出栈溢出了。所以可以采取先反转链表，再输出的方法。至于输出完了要不要再转回去，就看数据还有没有人要用了。不过从原则上来说，既然要求设计的是逆序输出链表，就不应该改变原始数据，应该在处理完了以后把链表给转回来的。本题中的数据时一次性的，我索性输出完了就给释放掉了。
　　时间复杂度O(n)，空间复杂度O(1)。

 // 650320    zhuli19901106    1511    Accepted    点击此处查看所有case的执行结果    5088KB    731B    90MS

 //

 #include <cstdio>

 #include <vector>

 using namespace std;

 class ListNode{

 public:

     int val;

     ListNode *next;

     ListNode(int _val = ) : val(_val), next(NULL){}

 };

 int main()

 {

     ListNode *root;

     ListNode *tail;

     int n;

     vector<ListNode *> vv;

     root = new ListNode();

     tail = root;

     vv.clear();

     while(scanf("%d", &n) ==  && n >= ){

         tail->next = new ListNode(n);

         tail = tail->next;

         vv.push_back(tail);

     }

     while(vv.size() > ){

         printf("%d\n", vv[vv.size() - ]->val);

         vv.pop_back();

     }

     tail = root;

     while(tail != NULL){

         root = tail->next;

         delete tail;

         tail = root;

     }

     return ;

 }

秒客网

剑指Offer - 九度1511 - 从尾到头打印链表

相关文章