206. 反转链表
查看题目简单
链表
递归
频率: 712
解法一：迭代法
时间复杂度：O(n) | 空间复杂度：O(1) | 推荐使用
动画演示
准备就绪 - 输入链表值（用逗号分隔），然后点击开始
代码实现
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
/**
* 迭代法反转链表
* 使用三个指针：prev、curr、next
*/
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
时间复杂度：O(n)
空间复杂度：O(1)
算法思路：
迭代法反转链表是一种直观且高效的解法，使用三个指针来逐步反转链表。
核心思想：
1. 使用三个指针：
- prev: 指向前一个节点，初始为null
- curr: 指向当前节点，初始为head
- next: 指向下一个节点，用于保存curr.next
2. 遍历过程：
- 保存当前节点的下一个节点（next = curr.next）
- 将当前节点的next指向前一个节点（curr.next = prev）
- 移动prev和curr指针（prev = curr, curr = next）
- 重复直到curr为null
3. 返回结果：
- prev指针指向反转后的链表头节点
复杂度分析：
- 时间复杂度：O(n)
- 需要遍历链表一次，每个节点访问一次
- 空间复杂度：O(1)
- 只使用了三个指针变量，不依赖链表长度
解法二：递归法
时间复杂度：O(n) | 空间复杂度：O(n)
动画演示
准备就绪 - 输入链表值（用逗号分隔），然后点击开始
代码实现
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class 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;
}
}
时间复杂度：O(n)
空间复杂度：O(n)
算法思路：
递归法反转链表是一种优雅的解法，通过递归到链表末尾，然后逐层返回并反转链表。
核心思想：
1. 递归终止条件：
- 如果head为null或head.next为null，直接返回head
- 这是递归的基准情况
2. 递归过程：
- 递归调用reverseList(head.next)，得到反转后的新头节点newHead
- 此时head.next指向的节点已经反转完成
3. 反转操作：
- 将head.next.next指向head（将下一个节点的next指向当前节点）
- 将head.next置为null（断开当前节点与下一个节点的连接）
- 返回newHead（新的头节点）
4. 递归调用栈：
- 递归会一直深入到链表末尾
- 然后从末尾开始逐层返回并执行反转操作
复杂度分析：
- 时间复杂度：O(n)
- 需要遍历链表一次，每个节点访问一次
- 空间复杂度：O(n)
- 递归调用栈的深度为n，需要O(n)的额外空间