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
