# 从尾到头打印链表
# 一、题目描述
输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
示例 1: 输入:head = [1,3,2] 输出:[2,3,1]
# 二、解题思路
1、辅助栈法
链表特点: 只能从前至后访问每个节点。 题目要求: 倒序输出节点值。 这种 先入后出 的需求可以借助 栈 来实现。
var reversePrint = function(head) {
let result = [];
while(head) {
result.unshift(head.val);
head = head.next;
}
return result;
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
复杂度分析:
- 时间复杂度:O(n)
- 空间复杂度:O(n)
2、递归法
利用递归: 先走至链表末端,回溯时依次将节点值加入列表 ,这样就可以实现链表值的倒序输出。
var reversePrint = function(head) {
return head == null ? [] : reversePrint(head.next).concat(head.val);
}
1
2
3
2
3
复杂度分析:
- 时间复杂度 O(N): 遍历链表,递归 N 次。
- 空间复杂度 O(N): 系统递归需要使用 O(N) 的栈空间。
3、双指针(反转链表)
- 定义两个指针: pre 和 cur ;pre 在前 cur 在后。
- 每次让 pre 的 next 指向 cur ,实现一次局部反转
- 局部反转完成之后, pre 和 cur 同时往前移动一个位置
- 循环上述过程,直至 pre 到达链表尾部
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let pre = null;
let curr = head;
while (curr) {
let tmpNext = curr.next; // 1.临时保存下一个节点指针
curr.next = pre; // 2.反转当前节点指向
pre = curr; // 3.pre指针右移
curr = tmpNext; // 4. curr指针右移
}
return pre;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
二、简洁的递归