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

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 head == nil || head.Next == nil {
		return head
	}
	// 为了保证全翻转的情况，增加一个虚拟头节点，方便记录头的位置
	head = &ListNode{
		Val:  0,
		Next: head,
	}

	resHead := head // 记录初始的头节点
	startHead := head // 记录操作前的上一个位置

	// 首先找到开始进行翻转的位置
	for i := 1; i <= m; i++ {
		startHead = head
		head = head.Next
	}

	// 开始进行翻转了
	var prev *ListNode
	reverseTail := head // 反转的尾节点
	cur := head
	for i := 0; i <= n-m && cur != nil; i++ {
		next := cur.Next
		cur.Next = prev
		prev = cur
		cur = next
	}

	// 重新链接翻转后的链表
	startHead.Next = prev // prev 是反转链表的头节点
	reverseTail.Next = cur // cur 是区间的下一个节点
	return resHead.Next
}