题目描述
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。网站的建设创新互联建站专注网站定制,经验丰富,不做模板,主营网站定制开发.小程序定制开发,H5页面制作!给你焕然一新的设计体验!已为成都铜雕雕塑等企业提供专业服务。
注：设链表长度为n。语言：C++
链表结点数据结构规定如下：
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };解法1：正向遍历，借助反向迭代器实现序列逆置（C++特性）。
vector printListFromTailToHead(ListNode* head) {
ListNode *p;
p = head;
vector array;
while(p != NULL)
{
array.push_back(p->val);
p = p->next;
}
return vector(array.rbegin(), array.rend());
} 时间复杂度：O(n)，空间复杂度：O(1)
解法2：借助栈先进后出的特性，将链表结点先入栈后出栈，再压入序列中。
vector printListFromTailToHead(ListNode* head) {
ListNode *p;
p = head;
stack s;
while(p != NULL)
{
s.push(p->val);
p = p->next;
}
p = head;
vector array;
while(p != NULL)
{
array.push_back(s.top());
s.pop();
p = p->next;
}
return array;
} 时间复杂度：O(n)，空间复杂度：O(n)
解法3：递归
vector array;
vector printListFromTailToHead(ListNode* head) {
ListNode *p;
p = head;
if(head != NULL)
{
if(head->next != NULL)
printListFromTailToHead(head->next);
array.push_back(head->val);
}
return array;
} 时间复杂度：O(n)，空间复杂度：O(n)
另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。