(链表)反转链表2

这里我们使用递归的思想来进行计算

参考：递归反转链表的一部分 - labuladong的算法小抄 (gitbook.io)

// @Description 反转链表 https://leetcode-cn.com/problems/reverse-linked-list-ii/
// @Author 小游
// @Date 2021/01/26
package main

import "fmt"

// 自己定义的链表
type ListNode struct {
	Val int
 	Next *ListNode
}

var succesor *ListNode

func reverseN(head *ListNode,n int) *ListNode  {
	if n == 1{
		succesor = head.Next
		return head
	}
	// 反转next的前n-1个节点
	last:=reverseN(head.Next,n-1)
	// 这里就是把当前的节的后一个节点的后一个节点置为当前节点
	head.Next.Next = head
	// 我们把后继节点给接上去
	head.Next = succesor
	// 返回拼接后的节点
	return last
}

func reverseBetween(head *ListNode, m int, n int) *ListNode {
	if m==1 {
		return 	reverseN(head,n)
	}
	head.Next = reverseBetween(head.Next,m-1,n-1)
	return head
}

func main()  {
	node:=new(ListNode)
	first:=node
	node.Val = 1
	node.Next = new(ListNode)
	node=node.Next
	node.Val = 2
	node.Next = new(ListNode)
	node=node.Next
	node.Val = 3
	node.Next = new(ListNode)
	node=node.Next
	node.Val = 4
	node.Next = new(ListNode)
	node=node.Next
	node.Val = 5
	last:=reverseBetween(first,2,3)
	fmt.Println(last)
}