0092. 反转链表 II #
- 标签:链表
- 难度:中等
题目大意 #
描述:给定单链表的头指针 head
和两个整数 left
和 right
,其中 left <= right
。
要求:反转从位置 left
到位置 right
的链表节点,返回反转后的链表 。
说明:
- 链表中节点数目为
n
。 - $1 \le n \le 500$。
- $-500 \le Node.val \le 500$。
- $1 \le left \le right \le n$。
示例:
- 示例 1:
|
|
解题思路 #
在「 0206. 反转链表」中我们可以通过迭代、递归两种方法将整个链表反转。这道题而这道题要求对链表的部分区间进行反转。我们同样可以通过迭代、递归两种方法将链表的部分区间进行反转。
思路 1:迭代 #
我们可以先遍历到需要反转的链表区间的前一个节点,然后对需要反转的链表区间进行迭代反转。最后再返回头节点即可。
但是需要注意一点,如果需要反转的区间包含了链表的第一个节点,那么我们可以事先创建一个哑节点作为链表初始位置开始遍历,这样就能避免找不到需要反转的链表区间的前一个节点。
这道题的具体解题步骤如下:
- 先使用哑节点
dummy_head
构造一个指向head
的指针,使得可以从head
开始遍历。使用index
记录当前元素的序号。 - 我们使用一个指针
reverse_start
,初始赋值为dummy_head
。然后向右逐步移动到需要反转的区间的前一个节点。 - 然后再使用两个指针
cur
和pre
进行迭代。pre
指向cur
前一个节点位置,即pre
指向需要反转节点的前一个节点,cur
指向需要反转的节点。初始时,pre
指向reverse_start
,cur
指向pre.next
。 - 当当前节点
cur
不为空,且index
在反转区间内时,将pre
和cur
的前后指针进行交换,指针更替顺序为:- 使用
next
指针保存当前节点cur
的后一个节点,即next = cur.next
; - 断开当前节点
cur
的后一节点链接,将cur
的next
指针指向前一节点pre
,即cur.next = pre
; pre
向前移动一步,移动到cur
位置,即pre = cur
;cur
向前移动一步,移动到之前next
指针保存的位置,即cur = next
。- 然后令
index
加1
。
- 使用
- 继续执行第
4
步中的1
、2
、3
、4
、5
步。 - 最后等到
cur
遍历到链表末尾(即cur == None
)或者遍历到需要反转区间的末尾时(即index > right
) 时,将反转区间的头尾节点分别与之前保存的需要反转的区间的前一个节点reverse_start
相连,即reverse_start.next.next = cur
,reverse_start.next = pre
。 - 最后返回新的头节点
dummy_head.next
。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。其中 $n$ 是链表节点个数。
- 空间复杂度:$O(1)$。
思路 2:递归算法 #
1. 翻转链表前 n 个节点 #
-
当
left == 1
时,无论right
等于多少,实际上都是将当前链表到right
部分进行翻转,也就是将前right
个节点进行翻转。 -
我们可以先定义一个递归函数
reverseN(self, head, n)
,含义为:将链表前第 $n$ 个节点位置进行翻转。- 然后从
head.next
的位置开始调用递归函数,即将head.next
为头节点的链表的的前 $n - 1$ 个位置进行反转,并返回该链表的新头节点new_head
。 - 然后改变
head
(原先头节点)和new_head
(新头节点)之间的指向关系,即将head
指向的节点作为head
下一个节点的下一个节点。 - 先保存
head.next
的next
指针,也就是新链表前 $n$ 个节点的尾指针,即last = head.next.next
。 - 将
head.next
的next
指针先指向当前节点head
,即head.next.next = head
。 - 然后让当前节点
head
的next
指针指向last
,则完成了前 $n - 1$ 个位置的翻转。
- 然后从
-
递归终止条件:当
n == 1
时,相当于翻转第一个节点,直接返回head
即可。 -
翻转链表
[left, right]
上的节点。 #
接下来我们来翻转区间上的节点。
- 定义递归函数
reverseBetween(self, head, left, right)
为
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。最多需要 $n$ 层栈空间。