-
题目链接: 从尾到头打印链表
题目描述
输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
提示
以下方法都是针对不带头结点,如有问题,欢迎指正。 -
思路1
我们知道栈是有后进先出特性的,所以遍历链表,将链表元素值入栈,然后将栈中元素弹出到目标ArrayList;
class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { stack<int> s; vector<int> result; while(head!=NULL){ s.push(head->val); head = head->next; } while(!s.empty()){ result.push_back(s.top()); s.pop(); } return result; } };
-
思路2
我们可以利用递归的思想来遍历,借鉴之后的二叉树递归遍历
class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { vector <int> result; if(head==nullptr){ return result; } result = printListFromTailToHead(head->next); result.push_back(head->val) return result; } };
-
思路3
我们直接将链表用头插法逆置,然后遍历
class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { vector<int> result; ListNode* p = head; head = nullptr; while(p!=nullptr){ ListNode* tmp = p->next; p->next = head; head = p; p = tmp; } while(head!=nullptr){ result.push_back(head->val); head = head->next; } return result; } };
-
思路4
与思路3不同之处在于链表逆置的方法不不同,通过双指针来逆置
class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { ListNode* pre = nullptr; ListNode* cur = head; ListNode* tmp = head; while(cur!=nullptr){ tmp = cur->next; cur->next = pre; pre = cur; cur = tmp; } vector<int> result; while(pre != nullptr){ result.push_back(pre->val); pre = pre->next; } return result; } };