题解 | #链表中的节点每k个一组翻转#

package main


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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param k int整型
 * @return ListNode类
 */
func reverseKGroup( head *ListNode ,  k int ) *ListNode {
    // 使用递归
    // 找到第一组尾部
    node := head
    // 每次从进入函数的头节点优先遍历链表k次，分出一组，若是后续不足k个节点，不用反转直接返回头
    if node == nil || node.Next == nil {
        return head
    }
    for i := 1; i < k; i++ {
        if node.Next == nil {
            return head
        }
        node = node.Next
    }
    temp := node.Next
    node.Next = nil
    // 从进入函数的头节点开始，依次反转接下来的一组链表
    newHead := revers(head)
    // 这一组经过反转后，原来的头变成了尾，后面接下一组的反转结果，下一组采用上述递归继续
    head.Next = reverseKGroup(temp, k)
    return newHead
}

// 反转链表
func revers(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    var pre *ListNode
    cur := head
    for cur != nil {
        pre, cur, cur.Next = cur, cur.Next, pre
    }
    return pre
}