题解 | #牛群的重新分组#

知识点：链表反转

解题思路：先判断当前区间是否需要反转，不需要就直接返回。需要就调用反转函数reverse。之后将后续区间交给reverseKGroup函数处理

package main

import . "nc_tools"

/*
 * 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
	if head == nil {
		return head
	}
	pre, cur := head, head
	for i := 0; i < k; i++ {
		// 不是k的整数倍，不反转，直接返回
		if cur == nil {
			return head
		}
		cur = cur.Next
	}
	newHead := reverse(pre, cur)
	pre.Next = reverseKGroup(cur, k)
	return newHead
}
func reverse(a, b *ListNode) *ListNode {
	pre, cur, next := (*ListNode)(nil), a, a
	for cur != b {
		next = cur.Next
		cur.Next = pre
		pre, cur = cur, next
	}
	return pre
}