0092.反转链表 II

https://leetcode.cn/problems/reverse-linked-list-ii/

方法一：递归

时间复杂度 $O(right)$，空间复杂度 $O(right)$。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
	var poster *ListNode
	var reverseN func(head *ListNode, n int) *ListNode
	reverseN = func(head *ListNode, n int) *ListNode {
		if n == 1 {
			poster = head.Next
			return head
		}
		ans := reverseN(head.Next, n-1)
		head.Next.Next, head.Next = head, poster
		return ans
	}

	if left == 1 {
		return reverseN(head, right)
	}
	head.Next = reverseBetween(head.Next, left-1, right-1)
	return head
}