206. 反转链表
题目描述
给你单链表的头节点 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
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
方法一：双指针
只需要改变链表的next指针的指向，直接将链表反转即可，时间复杂度 O(n)，空间复杂度 O(n)。其中 n 为链表的长度。
图示如下：
可视化演示
以
head = [1, 2, 3, 4, 5]为例，演示双指针反转：prev为已反转的链表，curr为剩余待反转链表，每轮把curr头节点摘下接到prev之前。蓝色为刚反转的节点，黄色为下一个待处理节点。点击 ▶ 播放，或逐步操作。
初始化：prev = null，curr = head = 1。head = [1,2,3,4,5]。
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
head = prev;
return head;
}
}class Solution {
reverseList(head: ListNode | null): ListNode | null {
if (head === null) {
return head;
}
let prev: ListNode | null = null;
let curr: ListNode | null = head;
while (curr !== null) {
const next: ListNode | null = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}方法二：头插法
创建虚拟头节点
时间复杂度
图示如下：
可视化演示
以
head = [1, 2, 3, 4, 5]为例，演示头插法反转：dummy为虚拟头节点，每轮把curr的头节点摘下插入dummy之后，最终dummy.next即为反转后的链表。蓝色为刚插入的节点。点击 ▶ 播放，或逐步操作。
初始化：dummy = new ListNode()，curr = head = 1。head = [1,2,3,4,5]。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode();
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = dummy.next;
dummy.next = curr;
curr = next;
}
return dummy.next;
}
}class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* dummy = new ListNode();
ListNode* curr = head;
while (curr) {
ListNode* next = curr->next;
curr->next = dummy->next;
dummy->next = curr;
curr = next;
}
return dummy->next;
}
};function reverseList(head: ListNode | null): ListNode | null {
if (head == null) {
return head;
}
let pre = null;
let cur = head;
while (cur != null) {
const next = cur.next;
cur.next = pre;
[pre, cur] = [cur, next];
}
return pre;
}方法三：从前向后递归
时间复杂度 O(n)，空间复杂度 O(n)。其中 n 为链表的长度。
可视化演示
以
head = [1, 2, 3, 4, 5]为例，演示从前向后递归反转：递归函数rescursion(prev, curr)思路与双指针法一致，每层把curr头节点接到prev之前，再递归处理剩余部分。蓝色为刚反转的节点，黄色为下一个待处理节点。点击 ▶ 播放，或逐步操作。
调用 rescursion(null, head)：prev = null，curr = head = 1。
class Solution {
public ListNode reverseList(ListNode head) {
return rescursion(null, head);
}
private ListNode rescursion(ListNode prev, ListNode curr) {
if (curr == null) {
return prev;
}
ListNode next = curr.next;
curr.next = prev;
return rescursion(curr, next);
}
}方法四：从后向前递归
递归反转链表的第二个节点到尾部的所有节点，然后
时间复杂度
可视化演示
以
head = [1, 2, 3, 4, 5]为例，演示从后向前递归反转：先递归反转head.next得到ans，回溯时再把head节点接到ans末尾。蓝色为当前正在接回的节点，绿色为已反转部分。点击 ▶ 播放，或逐步操作。
reverseList([1,2,3,4,5])：head=1，head.next=2 非空，递归 reverseList(head.next)=reverseList([2,3,4,5])。
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 递归调用，翻转第二个节点开始往后的链表
ListNode ans = reverseList(head.next);
// 翻转头节点与第二个节点的指向
head.next.next = head;
//此时的 head 节点为尾节点，next 需要指向 NULL
head.next = null;
return ans;
}
}class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* ans = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return ans;
}
};const rev = (pre: ListNode | null, cur: ListNode | null): ListNode | null => {
if (cur == null) {
return pre;
}
const next = cur.next;
cur.next = pre;
return rev(cur, next);
};
function reverseList(head: ListNode | null): ListNode | null {
if (head == null) {
return head;
}
const next = head.next;
head.next = null;
return rev(head, next);
}class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
ans = self.reverseList(head.next)
head.next.next = head
head.next = None
return ans方法五：使用栈
时间复杂度
可视化演示
以
head = [1, 2, 3, 4, 5]为例，演示用栈反转：先把所有节点依次入栈，再依次弹出并重建新链表。top指向栈顶，newHead为新链表头，current指向已重建的末尾。蓝色为当前弹出的节点，红色为最终结果。点击 ▶ 播放，或逐步操作。
初始化：stack = new Stack<>()，current = head = 1。开始遍历链表，依次入栈。
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
Stack<ListNode> stack = new Stack<>();
ListNode current = head;
while (current != null) {
stack.push(current);
current = current.next;
}
ListNode newHead = stack.pop();
current = newHead;
while (!stack.isEmpty()) {
ListNode node = stack.pop();
current.next = node;
current = node;
}
current.next = null;
return newHead;
}
}class Solution {
reverseList(head: ListNode | null): ListNode | null {
if (head === null || head.next === null) {
return head;
}
const stack: ListNode[] = [];
let current: ListNode | null = head;
while (current !== null) {
stack.push(current);
current = current.next;
}
const newHead: ListNode = stack.pop()!;
current = newHead;
while (stack.length > 0) {
const node = stack.pop()!;
current.next = node;
current = node;
}
current.next = null;
return newHead;
}
}