从尾到头打印链表
思路
第一种方案：
如果可以该表链表结构，可以先反转链表，然后从头到尾打印链表的值即可。
第二种方案：
从头到尾遍历链表的话，第一个遍历的需要最后被输出，最后一个遍历的需要第一个被输出，故我们可以利用栈后入先出的特性，把遍历的结构存入栈，最后出栈即是所求。
第三种方案：
既然思路2可以利用栈来解决问题，递归本质上也是栈的调用，所以利用递归也可以解答此题。
代码
第一种方案代码：
function reverseList(pHead) {
if (pHead === null) {
return null;
}
let cur = pHead;
let prev = null;
while (cur) {
const next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
function printReverseList(pHead) {
let newList = reverseList(pHead);
const res = [];
while (newList) {
res.push(newList.data);
newList = newList.next;
}
return res;
}
第二种方案代码：
function printListReversingly(pHead) {
if (pHead === null) return null;
const stack = [];
const res = [];
while (pHead !== null) {
stack.push(pHead.data);
pHead = pHead.next;
}
while (stack.length > 0) {
res.push(stack.pop());
}
return res;
}
第三种方案：
function printListReversingly_recursively(pHead, res = []) {
if (pHead === null) {
return null;
}
if (pHead !== null) {
if (pHead.next !== null) {
printListReversingly_recursively(pHead.next, res);
}
res.push(pHead.data);
}
return res;
}
复杂度分析
第一种方案：
- 时间复杂度：O(N)
- 空间复杂度: O(N)
第二种方案：
- 时间复杂度：O(N)
- 空间复杂度: O(N)
第三种方案：
- 时间复杂度: O(N)
- 空间复杂度: O(N)