题解 | #链表内指定区间反转#二次遍历#

package main

import . "nc_tools"

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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param m int整型
 * @param n int整型
 * @return ListNode类
 */
// 思路：找到关键节点pre、m、n、cur，再将m-n的部分反转，再拼接
// {11,12,13,14,15} m=2 n=4  pre.Val=11 m.Val=12 n.Val=14 cur.Val=15
func reverseBetween(head *ListNode, m int, n int) *ListNode {
	// write code here
	if head == nil || head.Next == nil {
		return head
	}

	dummy := &ListNode{Next: head}
	pre := dummy
	// 1. 走m-1步 -> 移动至m的前一个节点
	for i := 1; i < m; i++ {
		pre = pre.Next // 没执行一次循环，当前节点向后移动一位
	}

	nNode := pre
	// 2. 再向前移动 m-n+1位，移动至cur的前一个节点，即待反转区的最后一个节点 即n节点
	for i := m; i < n+1; i++ {
		nNode = nNode.Next
	}
	// 3. 获取关键节点 pre nNode mNode cur
	mNode := pre.Next // pre在第一个循环执行后，即为m的前一个节点，so m = pre.Next
	cur := nNode.Next

	// 4. 切断待反转区域前后链接
	pre.Next = nil
	nNode.Next = nil // mNode受影响，变为只有待反转区长度，

	// 5. 反转待反转区域，
	reverseList(mNode, cur)

	// 6. 拼接 pre + reverse
	pre.Next = nNode

	return dummy.Next

}
func reverseList(head *ListNode, cur *ListNode) *ListNode {
	for head != nil {
		next := head.Next
		head.Next = cur
		cur = head
		head = next
	}
	return cur
}