个人网站设计论文的结论,免费做电脑网站,尚仁网站建设,网站容量从尾到头打印链表信息卡片时间#xff1a;2020-03-23题目#xff1a;从尾到头打印链表tag#xff1a;list题目描述输入一个链表#xff0c;按链表从尾到头的顺序返回一个 ArrayList。01调用 reverse 函数解题思路这是一种简单粗暴的解法。先遍历一遍链表#xff0c;在遍历…从尾到头打印链表信息卡片时间2020-03-23题目从尾到头打印链表taglist题目描述输入一个链表按链表从尾到头的顺序返回一个 ArrayList。01调用 reverse 函数解题思路这是一种简单粗暴的解法。先遍历一遍链表在遍历链表的同时将当前指针指向的值放入 vector 数组中直到链表遍历完成。最后使用 reverse 函数将 vector 数组进行反转。public:vectorint printListFromTailToHead(ListNode* head) {vectorintArrayList;if(!head || !head-next)return {};while(head){ArrayList.push_back(head-val);headhead-next;}reverse(ArrayList.begin(),ArrayList.end());return ArrayList;}
};02调用 insert 函数解题思路与解法一有些类似依次从前往后遍历链表在遍历链表的同时调用 vector 的 insert 函数从头部插入此时链表指针指向的值。最后就得到了一个反转的数组。class Solution {
public:vectorint printListFromTailToHead(ListNode* head) {vectorintArrayList;if(head){ArrayList.insert(ArrayList.begin(),head-val);while(head-next){ArrayList.insert(ArrayList.begin(),head-next-val);headhead-next;}}return ArrayList;}
};03 调用栈方法解题思路创建一个元素为指针类型的栈来存放链表的指针。在遍历链表的同时将指针入栈此时栈的底部是链表的第一个元素栈顶是链表的最后一个元素。弹出栈的时候把指针指向的值放入 vector 数组里面。class Solution {
public:vectorint printListFromTailToHead(ListNode* head) {stackListNode* stackNodes;vectorint ArrayList;ListNode* phead;while (p ! NULL){stackNodes.push(p);p p-next;}while (!stackNodes.empty()){pstackNodes.top();ArrayList.push_back(p-val);stackNodes.pop();}return ArrayList;}
};04递归调用解题思路递归的本质就是一个栈结构可以用递归来实现。要实现反过来输出的链表我们每访问到一个节点的时候先递归输出它后面的节点再输出该节点自身这样就得到反转的链表。class Solution {
public:vectorint printListFromTailToHead(struct ListNode* head) {vectorint vec;printListFromTailToHead(head,vec);return vec;}void printListFromTailToHead(struct ListNode* head,vectorint vec) {if(head!nullptr){if(head-next!nullptr){printListFromTailToHead(head-next,vec);}vec.push_back(head-val);}}
};总结解法四递归的方法看起来比较简洁但是凡事都有利弊当链表非常长的时候就会导致函数调用的层级很深从而有可能导致函数调用栈溢出。解法一、解法二、解法三要优于解法四。
