1 题目
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
2 解析
（1）第一种：头插法
（2）第二种：迭代法，先截取中间部分，然后反转，再连接两头
（3）第三种：递归法
待更新
3 Python实现
class Solution:
# 方法一：头插法
'''
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
dummy = ListNode(-1)
dummy.next = head
prev = dummy
for _ in range(left-1):
prev = prev.next
curr = prev.next
for _ in range(right-left):
next_node = curr.next
curr = next_node.next
next_node.next = prev.next
prev.next = next_node
return dummy
'''
# 方法二：迭代法
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
def reverseList(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
prev = dummy_node
for _ in range(left-1):
prev = prev.next
right_node = prev
for _ in range(right-left+1):
right_node = right_node.next
# 保存节点
left_node = prev.next
curr = right_node.next
# 切断链表
prev.next = None
right_node.next = None
reverseList(left_node)
# 恢复连接
# 注意，此处右node变成了左node，左node变成了右node。
prev.next = right_node
left_node.next = curr
return dummy_node.next
