剑指 Offer 06. 从尾到头打印链表
题目链接：从尾到头打印链表。
目录
题目描述
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例1：
输入：head = [1,3,2]
输出：[2,3,1]限制：0 <= 链表长度 <= 10000
分析
输入一个链表，返回一个倒序的数组。这道题最先想到的肯定是使用一种数据结构来存储链表中的数据，再以倒叙输出到结果数组中去。
思路1
输入一串数字，倒叙输出。这种特性当 栈（Stack）莫属了。所以，可以遍历链表，将每个节点的值压入到一个栈中，之后再依次将数据弹栈到一个数组中。
代码
利用 栈 倒叙输出。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
std::stack<int> sk;
public:
vector<int> reversePrint(ListNode* head) {
while (head != NULL) {
sk.push(head->val);
head = head->next;
}
vector<int> vec;
while (!sk.empty()) {
vec.push_back(sk.top());
sk.pop();
}
return vec;
}
};
思路2
既然是要倒叙输出，那么如果知道一个数组的长度，也可以利用倒叙增长的下标来实现倒叙的访问。
所以可以循环遍历链表，得到链表的长度 len。之后创建一个长度为 len 的数组，依次遍历链表，并将数据从数组的末尾，也就是从 len-1 开始存放。遍历结束之后就得到了一个逆序排列的数组了。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
int len = 0;
ListNode* h = head;
while (h != NULL) {
len++;
h = h->next;
}
vector<int> v(len);
for (int i = len-1; i >= 0; i--) {
v.at(i) = head->val;
head = head->next;
}
return v;
}
};
思路3
如果是使用 C++，那么可以利用 vector 的 insert 特性，将每一个结点的值都插入到 vector 的头部，这样就实现的反转。
但是，此时的时间复杂度会比较高，因为每一次 vector 插入元素到头部，都需要移动剩余的元素位置。
代码
vector 头插法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int> v;
while (head != NULL) {
v.insert(v.cbegin(), head->val);
head = head->next;
}
return v;
}
};
思路4
为了解决思路3中时间复杂度高的问题，我们可以利用 vector 的构造函数（range3）来实现反转，传入两个范围迭代器。
如果将链表数据存到 vector1 中，那么就可以利用 vector vector2(vector1.rbegin(), vector1.rend()) 在 vector2 中实现数据的反转。
代码
利用 vector 的构造函数反转。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int> v;
while (head != NULL) {
v.push_back(head->val);
head = head->next;
}
vector<int> vt(v.rbegin(), v.rend());
return vt;
}
};
