题解的思路是先找到需要反转的子链表的起始节点和结束节点,然后将这一段子链表反转,最后将反转后的子链表重新连接到原链表中。具体步骤如下:
1. 创建一个虚拟头节点 dummy,指向原链表的头节点。
2. 定义两个指针 pre 和 a,初始时都指向 dummy。
3. 先将 pre 和 a 向右移动 left-1 次,使得 a 指向需要反转的子链表的前一个节点。
4. 定义指针 b,初始时指向 a,然后将 b 向右移动 right-left+1 次,使得 b 指向需要反转的子链表的后一个节点。
5. 调用 reverse 函数反转 a 和 b 之间的子链表。
6. 将反转后的子链表重新连接到原链表中,即将 pre.next 指向反转后的子链表头节点,将 a.next 指向 b。
7. 返回 dummy.next,即反转后的链表的头节点。
时间复杂度: O(right)
空间复杂度: O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
if head is None:
return head
# 创建虚拟头节点 dummy,指向原链表的头节点
dummy = ListNode(next=head)
# 定义指针 pre 和 a,初始时都指向 dummy
pre = dummy
a = head
# 将 pre 和 a 向右移动 left-1 次,使得 a 指向需要反转的子链表的前一个节点
for _ in range(left-1):
pre = pre.next
a = a.next
# 定义指针 b,初始时指向 a,然后将 b 向右移动 right-left+1 次,使得 b 指向需要反转的子链表的后一个节点
b = a
for _ in range(right-left+1):
b = b.next
# 定义反转链表的函数 reverse
def reverse(a, b):
pre = None
cur = a
while cur != b:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
# 调用 reverse 函数反转 a 和 b 之间的子链表
pre.next = reverse(a, b)
# 将反转后的子链表重新连接到原链表中
a.next = b
# 返回反转后的链表的头节点
return dummy.next