type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定单链表的头节点head,反转链表,并返回反转后的链表。
示例 1:

示例 2:

示例 3:
解法一:双指针 (推荐)
把
next指针逐个“掉头”。用两个指针维护已反转区和待处理区的边界:
prev指向已反转链表的表头(初始为None)
cur指向当前要掉头的节点
每次把
cur.next 改指向 prev,然后整体向前推进。复杂度
- 时间:
O(n)(每个节点只改一次指针)
- 空间:
O(1)(常数指针)
解法二:递归
先让后半段反转,再接上当前节点。
把“反转前半段 + 挂到后半段尾部”,交给递归的返回阶段完成。
复杂度
- 时间:
O(n)
- 空间:
O(n)(递归栈深度,最坏链型)
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-206-反转链表
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 204] 质数计数
下一篇
[Leetcode 208] 实现 Trie
