206. 反转链表 #10
Description
迭代
1.初始化哨兵节点 prev 为 null，及当前节点 curr 指向头节点。
2.开始迭代，记录 next 指针留备后用，反转指针。
3.推进指针继续迭代，最后返回新的链表头节点 prev。
const reverseList = function(head) {
let prev = null;
let curr = head;
while (curr !== null) {
// 记录 next 节点
let next = curr.next;
// 反转指针
curr.next = prev;
// 推进指针
prev = curr;
curr = next;
}
// 返回翻转后的头节点
return prev;
};- 时间复杂度: O(n)
- 空间复杂度: O(1)
递归
const reverseList = function(head) {
if (!head || !head.next) return head;
// 记录当前节点的下一个节点
let next = head.next;
let reverseHead = reverseList(next);
// 操作指针进行反转
head.next = null;
next.next = head;
return reverseHead;
};- 时间复杂度: O(n)
- 空间复杂度: O(n)