6. 从尾到头打印链表
1. 描述
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
2. 例子
示例 1:
输入：head = [1,3,2]
输出：[2,3,1]
3. 限制
- 0 <= 链表长度 <= 10000
4. 题解
n 是 m_head 中存在的节点个数
时间复杂度: O(n)
空间复杂度: O(1)
先反转链表再遍历，或者先遍历再反转数组。空间复杂度指的是算法在运行过程中辅助变量所占用的空间，但是例如本题，它提供的是一个链表，而要求返回的则是一个数组，不管任谁来，它都必须额外消耗这个需要返回的数组的空间。就本题来说，我的两个做法分别是先把链表反转再遍历存入数组，和先遍历链表存入数组再反转。其中，先反转链表的话，它的计算过程是仅需要消耗常数空间的，最后存入数组是题目要求而不得已的事情；而先存入数组再反转的话，这个数组是计算过程本身就需要的，即使我们的题目不要求存入数组而只是遍历，他也是需要这个数组的。所以，我个人（及我的妻子）的观点是，先反转再遍历的空间复杂度是 O(1)，而先遍历再反转的空间复杂度是 O(n)，这也是刷《剑指Offer》中所有题的空间复杂度标准，即因为题目要求返回特定格式数据而造成不可避免的空间开销不计入算法的空间复杂度。
class Solution
{
public:
// vector<int> reversePrint(ListNode* head)
vector<int> reversePrint(ListNode *m_head)
{
if(!m_head) return vector<int>{};
auto lastInvertedNode = m_head;
auto firstOriginNode = m_head->next;
lastInvertedNode->next = nullptr;
int nodeCount = 1;
while(firstOriginNode)
{
nodeCount++;
auto currentNode = firstOriginNode;
firstOriginNode = firstOriginNode->next;
currentNode->next = lastInvertedNode;
lastInvertedNode = currentNode;
}
vector<int> result(nodeCount);
for(int i = 0; lastInvertedNode; i++)
{
result[i] = lastInvertedNode->val;
lastInvertedNode = lastInvertedNode->next;
}
return result;
}
};