【LeetCode】206. 反转链表
1 题目描述
206. 反转链表要求给定单链表的头节点 head
,任务是反转链表,并返回反转后的链表。
2 解题思路
- 递归反转:使用递归方法,每次反转当前节点
cur
的next
指针,使其指向其前一个节点prev
。 - 终止条件:当
cur
指针为空时,递归结束,此时prev
指针即为反转后链表的头节点。 - 更新指针:每次递归调用返回后,更新
cur
和prev
的值,以便进行下一次反转操作。
3 Java 代码实现
public class Solution {
public ListNode reverseList(ListNode head) {
// 开始反转过程,初始时 prev 为 null
return reverse(head, null);
}
private ListNode reverse(ListNode cur, ListNode prev) {
// 当 cur 为空时,反转完成
if (cur == null)
return prev;
// 保存 cur 的下一个节点
ListNode temp = cur.next;
// 将 cur 的 next 指向 prev,完成一次反转
cur.next = prev;
// 递归地反转剩余的链表部分
return reverse(temp, cur);
}
}
- 时间复杂度: O(n),其中 n 是链表中的节点数。每个节点恰好被访问一次。
- 空间复杂度: O(n),这是由于递归栈需要 O(n) 的空间来保存每一次递归调用的信息。
4 注意事项
- 递归方法:使用递归方法来反转链表,这种方法简洁明了。
- 辅助方法:定义了一个辅助方法
reverse
,它接受当前节点cur
和前一个节点prev
作为参数。 - 基线条件:当
cur
为空时,返回prev
作为新的头节点。 - 递归调用:在递归调用中,先保存
cur.next
,然后将cur.next
指向prev
,再递归调用reverse
方法处理下一个节点。