0206. 反转链表 #
- 标签:链表
- 难度:简单
题目大意 #
描述:给定一个单链表的头节点 head
。
要求:将该单链表进行反转。可以迭代或递归地反转链表。
说明:
- 链表中节点的数目范围是 $[0, 5000]$。
- $-5000 \le Node.val \le 5000$。
示例:
- 示例 1:
|
|
解题思路 #
思路 1:迭代 #
-
使用两个指针
cur
和pre
进行迭代。pre
指向cur
前一个节点位置。初始时,pre
指向None
,cur
指向head
。 -
将
pre
和cur
的前后指针进行交换,指针更替顺序为:- 使用
next
指针保存当前节点cur
的后一个节点,即next = cur.next
; - 断开当前节点
cur
的后一节点链接,将cur
的next
指针指向前一节点pre
,即cur.next = pre
; pre
向前移动一步,移动到cur
位置,即pre = cur
;cur
向前移动一步,移动到之前next
指针保存的位置,即cur = next
。
- 使用
-
继续执行第 2 步中的 1、2、3、4。
-
最后等到
cur
遍历到链表末尾,即cur == None
,时,pre
所在位置就是反转后链表的头节点,返回新的头节点pre
。
使用迭代法反转链表的示意图如下所示:
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。
思路 2:递归 #
具体做法如下:
- 首先定义递归函数含义为:将链表反转,并返回反转后的头节点。
- 然后从
head.next
的位置开始调用递归函数,即将head.next
为头节点的链表进行反转,并返回该链表的头节点。 - 递归到链表的最后一个节点,将其作为最终的头节点,即为
new_head
。 - 在每次递归函数返回的过程中,改变
head
和head.next
的指向关系。也就是将head.next
的next
指针先指向当前节点head
,即head.next.next = head
。 - 然后让当前节点
head
的next
指针指向None
,从而实现从链表尾部开始的局部反转。 - 当递归从末尾开始顺着递归栈的退出,从而将整个链表进行反转。
- 最后返回反转后的链表头节点
new_head
。
使用递归法反转链表的示意图如下所示:
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n)$
- 空间复杂度:$O(n)$。最多需要 $n$ 层栈空间。