面试题5：从尾到头打印链表

提交网址：  

本题知识点： 

题目描述

输入一个链表，从尾到头打印链表每个节点的值。 

输入描述:

输入为链表的表头

输出描述:

输出为需要打印的“新链表”的表头

分析：

此题要求返回类型为vector<int>，故有两种方法：

1. 使用vector容器在头部进行插入，模拟堆栈;

2. 使用递归思想实现。

AC代码：

class Solution {public:    vector
    
      printListFromTailToHead(struct ListNode* head) {                vector
     
       vec;        ListNode *p;                p=head;        while(p!=NULL)        {            vec.insert(vec.begin(), p->val);  // 每次都在向量的开头进行插入            p=p->next;        }        return vec;    }};
     
    

如果想使用stack容器的话，可以这样写：

void printListFromTailToHead(ListNode *head){	if(head==NULL) return head;	std::stack 
    
      s;	ListNode *p;	while(p!=NULL)		{			s.push(p);      // 顶部插入			p=p->next;		}	while(!s.empty())	{		p=s.top();                  // 获取到栈顶的结点(指针类型)		cout<
     
      val<<" ";  // printf("%d\t",p->val);		s.pop();                     // pop()：出栈，删除栈顶元素	}}