206. 反转链表
题目描述
输入单链表的头节点 head。把链表的方向整个倒过来，返回新的头节点。空链表返回 null。
链表以数组形式表示，例如 [1,2,3]。
示例 1
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
解释：反转后节点顺序为 5、4、3、2、1。
示例 2
输入：head = [1,2] 输出：[2,1]
解释：两个节点交换了先后。
示例 3
输入：head = [] 输出：[]
解释：空链表反转后仍为空。
数据范围
- 节点数在
[0, 5000]范围内。 -5000 <= Node.val <= 5000
进阶：迭代和递归都能实现反转，你能分别写出两种做法吗？
解题思路：迭代（三指针）
迭代维护 prev 和 cur。先保存 cur.next，再把 cur.next 指向 prev，最后同步前进两个指针。
为什么正确
每轮结束时，prev 指向已反转的前缀，cur 指向尚未处理的后缀。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
修改 next 前必须先保存后继节点，否则剩余链表会丢失。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def reverseList(self, head):
prev = None
cur = head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prevclass Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while (cur != null) {
ListNode nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
}class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
};func reverseList(head *ListNode) *ListNode {
var prev *ListNode
cur := head
for cur != nil {
nxt := cur.Next
cur.Next = prev
prev = cur
cur = nxt
}
return prev
}var reverseList = function(head) {
let prev = null;
let cur = head;
while (cur) {
const nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev;
};function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let cur = head;
while (cur) {
const nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev;
};其他解法
迭代从前往后逐个改变指针方向，空间 O(1)；递归先一直走到链表末尾，在返回时从后往前改变指针，需要 O(n) 栈空间。
解法 2：递归 时间 O(n)，空间 O(n)
先递归反转 head.next 开始的链表，得到新的头结点 newHead。此时 head.next 是反转后链表的尾结点，令 head.next.next = head，把 head 接到尾部，再把 head.next 设为空。空链表或只有一个结点时直接返回 head。
体现了“假设子问题已解决”的递归思想，代码简洁。需要 O(n) 递归栈，head.next.next = head 这一步不太好理解，需要画图。
from typing import Optional
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
new_head = self.reverseList(head.next)
head.next.next = head
head.next = None
return new_headclass Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newHead := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return newHead
}var reverseList = function(head) {
if (!head || !head.next) return head;
const newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
};function reverseList(head: ListNode | null): ListNode | null {
if (!head || !head.next) return head;
const newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
};