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

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 {
    // write code here
    if head == nil || m == n {
        return head
    }

    // 构造虚拟节点
    dummy := &ListNode{Next: head}
    prevM := dummy
    //  确定 m 的前置节点
    for i := 0; i < m -1; i++ {
        prevM = prevM.Next
    }

    // 找到 m 节点，准备开始反转
    // 1-2-3-4-5 反转 2,4，即每次选择2之后的数据插入2之前
    curr := prevM.Next // 2节点 
    for i := 0; i < n - m; i++ {
        temp := curr.Next // 3节点
        curr.Next = temp.Next // 2节点 指向 4节点 1-2-4-5
        temp.Next = prevM.Next // 3节点 指向 2节点 3-2-4-5   
        prevM.Next = temp  // 1节点 指向 3节点 1-3-2-4-5
    }
    return dummy.Next
}