从尾到头打印链表1

题目要求从尾到头地遍历并打印一个单链表的节点值，即将链表的节点值以反向的顺序存入数组并返回。这里我们分析一下如何实现这个功能。 我们需要定义链表节点的结构。在C++中，单链表节点通常由一个整型变量`val`表示节点值，以及一个指向下一个节点的指针`next`构成。题目中给出的部分代码已经定义了`ListNode`结构体： ```cpp struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ``` 接下来，我们需要创建一个`Solution`类，并在其中实现`reversePrint`函数，该函数接受链表的头节点`head`作为参数，返回一个包含反向节点值的数组。我们可以使用栈（stack）数据结构来辅助完成这个任务，因为栈具有后进先出（LIFO）的特性，正好可以用来将链表的节点值按照从尾到头的顺序存储。 以下是对`reversePrint`函数的完整实现： ```cpp class Solution { public: vector<int> reversePrint(ListNode* head) { stack<int> s; vector<int> ret; // 检查头节点是否为空 if (head == nullptr) { return ret; } // 遍历链表并将节点值压入栈中 while (head != nullptr) { s.push(head->val); head = head->next; } // 将栈中的元素依次弹出，存入结果数组 while (!s.empty()) { ret.push_back(s.top()); s.pop(); } return ret; } }; ``` 在这个实现中，我们首先创建一个空栈`s`和一个空的结果数组`ret`。然后，我们遍历链表，将每个节点的值压入栈中。由于栈是后进先出的，所以链表的最后一个节点会被最先压入栈底，而第一个节点则被压在栈顶。当链表遍历完成后，我们再依次将栈中的元素弹出，存入结果数组`ret`，这样就可以得到一个从尾到头的节点值序列。 例如，对于输入`head = [1, 3, 2]`，初始链表为`1 -> 3 -> 2`，遍历过程中栈的变化为`[2] -> [3, 2] -> [1, 3, 2]`，最后栈为空时，数组`ret`中的顺序为`[2, 3, 1]`，即反向的链表节点值。 这个方法的时间复杂度是O(n)，其中n是链表的长度，因为我们只遍历一次链表。空间复杂度也是O(n)，因为最多需要存储n个节点值在栈中。