反转链表
🟢 简单题目描述
给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
示例 1
输入：head = [1, 2, 3, 4, 5]
输出：[5, 4, 3, 2, 1]示例 2
输入：head = [1, 2]
输出：[2, 1]示例 3
输入：head = []
输出：[]提示
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
解法一
参考答案 (2 个标签)
迭代 O(n)
思路
使用三个指针：prev、curr、next，依次反转每个节点的指向。
代码实现
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
function reverseList(head) {
let prev = null;
let curr = head;
while (curr !== null) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}复杂度分析
- 时间复杂度：O(n)，遍历一次链表
- 空间复杂度：O(1)，只使用常数空间
图解
初始: 1 -> 2 -> 3 -> null
curr
prev=null
步骤1: null <- 1 2 -> 3 -> null
prev curr
步骤2: null <- 1 <- 2 3 -> null
prev curr
步骤3: null <- 1 <- 2 <- 3
prev curr=null
返回 prev解法二
参考答案 (2 个标签)
递归 O(n)
思路
递归到链表末尾，然后在回溯时反转指针方向。
代码实现
/**
* @param {ListNode} head
* @return {ListNode}
*/
function reverseList(head) {
if (head === null || head.next === null) {
return head;
}
const newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)，递归调用栈