package main
import "fmt"
/*
 * 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 {
    // write code here
    fmt.Println("start")
    defer fmt.Print("end")
    
    //1. 判断非主流情况
    if(head == nil || head.Next == nil){
        return head
    }
    
    //创建头节点
    pHeadNode := &ListNode{Next:head}
    pHead := pHeadNode
     
    for i := 1; i < m; i++ {
        pHead = pHead.Next
    }
 
    //当前结点
    cur := pHead.Next

    //反转
    for i := m; i < n; i++ {
        tmp := cur.Next
        //第一步 保住后面的链表
        cur.Next = tmp.Next
        //第二步 交换
        tmp.Next = pHead.Next
        //第三步 交换
        pHead.Next = tmp
    }
    
    return pHeadNode.Next
}

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

/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
*/
func ReverseList( pHead *ListNode ) *ListNode {
	// write code here
    fmt.Println("start")
    defer fmt.Print("end")
    
    //1. 判断非主流情况
    if(head == nil || head.Next == nil){
        return head
    }
    
    //2.定义新的链表
    var newList *ListNode
    
    for pHead != nil {
        //1. 保存后面的链表
        oldList := pHead.Next
        //2. 反转 1->nil 2->1->nil 3->2->1->nil
        pHead.Next = newList
        //3. 更新newList
        newList = pHead
        //4.缩短
        pHead = oldList;
    }
	
    return newList;
}

package main
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param k int整型 
  * @return ListNode类
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
	// write code here
// 	fmt.Println("start")
// 	defer fmt.Print("end")

	//判断非主流情况
	if head == nil || head.Next == nil {
		return head
	}

	//定义头指针
	pHead := &ListNode{Next: head}
	//定义四个指针
	var pre *ListNode = pHead
	var start *ListNode = head
	var end *ListNode = head
	var next *ListNode = head

	for next != nil {
		//找到end
		for i := 1; i < k && end != nil; i++ {
			end = end.Next
		}
		//发现end是nil就结束了
		if end == nil {
			break
		}
		//找到neext，也就是end的下一个
		next = end.Next
		//定义小段节链表的结尾
		end.Next = nil
		/**
		  交换头尾
		*/
		//反转玩start会是结尾，
		end = start
		//反转,start是3
		start = Reverse(start)

		//拼接
		end.Next = next
		pre.Next = start

		//继续移动四个变量
		pre = end
		start = next
		end = start
	}

	return pHead.Next
}

func Reverse(head *ListNode) *ListNode {
	//定义前中后
	var pre *ListNode = nil
	cur := head
	var next *ListNode = nil

	for cur != nil {
		next = cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}

	return pre
}