一. 题目

二. 思路

• 本质就是分段翻转链表。

• 保存当前段的前一个节点，比较方便。

三. 代码

class Solution
{
    public ListNode reverseKGroup(ListNode head, int k)
    {
        final ListNode vh = new ListNode();
        vh.next = head;

        int cnt;
        ListNode ph = vh, tail = null;//当前段的头结点的前一个节点和尾巴节点
        while (true)
        {
            cnt = 0;
            ListNode cur = ph.next;//检查是否这段有k个
            while (cur != null && cnt < k)
            {
                ++cnt;
                tail = cur;
                cur = cur.next;
            }
            if (cnt < k) break;

            ListNode pn = tail.next, sh = ph.next;//前一个节点和开始的头
            cur = ph.next;//当前节点
            ph.next = tail;//让上一个节点连到翻转后的头
            ph = sh;//ph下一次就是最初的头
            for (int i = 0; i < k; ++i)
            {
                ListNode ne = cur.next;//当前节点的下一个节点
                cur.next = pn;//当前节点指向前一个节点
                pn = cur;//前一个节点变为当前节点
                cur = ne;//当前节点到达下一个节点
            }
        }

        return vh.next;
    }
}

class Solution
{
    private static class RNode
    {
        ListNode head, tail, NHead;//翻转后当前段的头尾，以及下一段的起点

        public RNode(ListNode head, ListNode tail, ListNode NHead)
        {
            this.head = head;
            this.tail = tail;
            this.NHead = NHead;
        }
    }

    //返回反转后的头和尾巴
    RNode reverse(ListNode cur, int k)
    {
        ListNode ph = cur, pn = null, ne = null;
        for (int i = 0; i < k; i++)
        {
            ne = cur.next;
            cur.next = pn;
            pn = cur;
            cur = ne;
        }

        return new RNode(pn, ph, ne);
    }

    public ListNode reverseKGroup(ListNode head, int k)
    {
        ListNode vh = new ListNode(), pt = vh;//虚拟头以及上一段的尾巴
        while (head != null)
        {
            int cnt = 0;
            ListNode cur = head;
            while (cur != null && cnt < k)
            {
                ++cnt;
                cur = cur.next;
            }

            if (cnt < k)
            {
                pt.next = head;
                break;
            } else
            {
                RNode res = reverse(head, k);
                pt.next = res.head;
                pt = res.tail;
                head = res.NHead;
            }
        }
        return vh.next;
    }
}