一、题目简介

题目地址：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

二、解法

关键点：1、使用哨兵减少判断；2、使用数组简单的模拟栈的功能

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 思路 p1 从head开始遍历
// p2 每次从p1，开始遍历，用于判断剩下的长度是否大于k,
// 如果剩余节点大于 k,即p1于p2之间 一组
// 翻转 p1 到 p2 直接的节点
// p1 设置p2， 重新开始上面遍历
func reverseKGroup(head *ListNode, k int) *ListNode {
    if k <= 1 {
        return head
    }

    if head == nil || head.Next == nil {
        return head
    }

    p1 := head

    for p1.Next != nil {
        var p2 *ListNode
        if p1 == head {
            p2 = p1
        } else {
            p2 = p1.Next
        }

        // 判断是否还有 k个节点
        isExist := false // 如果不足k个节点，直接返回
        for i := 1; i < k; i++ {
            p2 = p2.Next
            if p2 == nil {
                isExist = true
                break
            }
        }

        if isExist { // 剩下节点不足k个节点不需要翻转
            break
        }

        // 翻转p1 ~ p2 之间的节点
        if p1 == head {
            // 添加一个哨兵
            p3 := &ListNode{
                Next: p1,
            }

            p1 = revertNodes(p3, p2)

            head = p2
        } else {
            p1 = revertNodes(p1, p2)
        }
    }

    return head
}

// 翻转 p1.Next 到 p2 直接的节点
// 返回 翻转后的最后一个节点
func revertNodes(p1, p2 *ListNode) *ListNode {
    p2Next := p2.Next
    // 基于数组，利用栈的特性实现翻转
    nodes := make([]*ListNode, 0)
    p3 := p1.Next
    for {
        nodes = append(nodes, p3)
        p3 = p3.Next
        if p3 == p2.Next {
            break
        }
    }

    nodesLen := len(nodes)
    for i := nodesLen - 1; i >= 0; i-- {
        p1.Next = nodes[i]
        p1 = nodes[i]
    }

    p1.Next = p2Next

    return p1
}