类型：链表
-
- 反转链表 II 💛
https://leetcode-cn.com/problems/reverse-linked-list-ii/
❓ 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
💡 两次遍历
第一次遍历，找到 left 和 right 的指针位置。
第二次遍历，反转 left 和 right 之间的链表。
class Solution: def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode: def reverse_linked_list(head: ListNode): # 也可以使用递归反转一个链表 pre = None cur = head while cur: next = cur.next cur.next = pre pre = cur cur = next # 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论 dummy_node = ListNode(-1) dummy_node.next = head pre = dummy_node # 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点 # 建议写在 for 循环里，语义清晰 for _ in range(left - 1): pre = pre.next # 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点 right_node = pre for _ in range(right - left + 1): right_node = right_node.next # 第 3 步：切断出一个子链表（截取链表） left_node = pre.next curr = right_node.next # 注意：切断链接 pre.next = None right_node.next = None # 第 4 步：同第 206 题，反转链表的子区间 reverse_linked_list(left_node) # 第 5 步：接回到原来的链表中 pre.next = right_node left_node.next = curr return dummy_node.next时间复杂度：O(n)，空间复杂度：O(1)
💡 一次遍历
一次遍历，直接完成反转。
class Solution: def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode: # 设置 dummyNode 是这一类问题的一般做法 dummy_node = ListNode(-1) dummy_node.next = head pre = dummy_node for _ in range(left - 1): pre = pre.next cur = pre.next for _ in range(right - left): next = cur.next cur.next = next.next next.next = pre.next pre.next = next return dummy_node.next时间复杂度：O(n)，空间复杂度：O(1)