【剑指Offer第三题】从尾到头打印链表
题目描述
输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
注:设链表长度为n。语言:C++
链表结点数据结构规定如下:
* struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) :* val(x), next(NULL) {* }* };
解法1:正向遍历,借助反向迭代器实现序列逆置(C++特性)。
vector<int> printListFromTailToHead(ListNode* head) { ListNode *p; p = head; vector<int> array; while(p != NULL) { array.push_back(p->val); p = p->next; } return vector<int>(array.rbegin(), array.rend()); }
时间复杂度:O(n),空间复杂度:O(1)
解法2:借助栈先进后出的特性,将链表结点先入栈后出栈,再压入序列中。
vector<int> printListFromTailToHead(ListNode* head) { ListNode *p; p = head; stack<int> s; while(p != NULL) { s.push(p->val); p = p->next; } p = head; vector<int> array; while(p != NULL) { array.push_back(s.top()); s.pop(); p = p->next; } return array; }
时间复杂度:O(n),空间复杂度:O(n)
解法3:递归
vector<int> array; vector<int> 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)
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。