题解 | #链表内指定区间反转#

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param m int整型 
  * @param n int整型 
  * @return ListNode类
*/
// func reverseBetween( head *ListNode ,  m int ,  n int ) *ListNode {
//     if m == n {
//         return head
//     }
//     dumny := &ListNode{Next:head}
//     p := dumny
//     i := 0
//     for i < m-1{
//         i++
//         p = p.Next
//     }
    
//     var next *ListNode
//     var f func(head *ListNode,m int,n int) *ListNode
//     f = func(head *ListNode,m int,n int) *ListNode {
//         if n == m {
//             next = head.Next
//             return head
//         }
        
//         last := f(head.Next,m,n-1)
//         head.Next.Next = head
//         head.Next = next
//         return last
//     }
    
//     p.Next = f(p.Next,m,n)
    
//     return dumny.Next
// }

var successor *ListNode
//先实现反转链表的前N的节点的函数
func reverseN(head *ListNode,n int) *ListNode { 
	if n == 1 {
		successor = head.Next
        return head
	}

	last := reverseN(head.Next,n-1)
	head.Next.Next = head
	head.Next = successor
	return last
}

//将指定区间的反转转换为 前N个节点的函数
func reverseBetween(head *ListNode, m, n int) *ListNode {
	if m == 1 {
		return reverseN(head,n)
	}
	head.Next = reverseBetween(head.Next , m-1, n-1)
	
	return head
}