力扣 25. K 个一组翻转链表

题目来源：https://leetcode.cn/problems/reverse-nodes-in-k-group/

大致题意：
给一个链表和整数 k，将链表从头开始每 k 个翻转一次，若最后一段个数不足 k 个，则无需翻转

思路

1. 设计一个翻转链表的函数，给定节点 node 和长度 k，可以将 node 开始的 k 个节点翻转。设计时需要注意，翻转后 node.next 需要指向翻转前该段链表最后一个节点的 next
2. 使用一个变量存下当前待翻转的链表段的开始节点，遍历原链表，每遍历 k 个时，进行翻转，翻转后需要注意，当前链表段首节点的前个节点的 next 需要指向翻转后的首节点

具体看代码

public ListNode reverseKGroup(ListNode head, int k) {
    
        if (head == null || k == 1) {
    
            return head;
        }
        // 当前遍历的节点数目
        int count = 0;
        // 当前翻转的链表段的开始节点
        ListNode newHead = head;
        // 当前遍历的节点
        ListNode cur = head;
        // 哨兵
        ListNode ans = new ListNode(-1);
        // 上一段翻转链表的尾节点
        ListNode lastTail = ans;
        while (cur != null) {
    
            // 更新遍历的节点数目
            count++;
            // 若遍历节点的数目等于 k，进行翻转
            if (count == k) {
    
                // 首先存下当前段原头节点，也就是反转后的尾节点
                ListNode newTail = newHead;
                // 反转链表，同时存下段翻转后的头节点
                newHead = reverse(newHead, k);
                // 上一段的尾节点的 next 要指向反转后的头节点
                lastTail.next = newHead;
                // 重置计数
                count = 0;
                // 更新上一段的尾节点
                lastTail = newTail;
                // 更新下一段翻转前的首节点
                newHead = newTail.next;
                // 更新当前遍历的位置
                cur = lastTail;
            }
            cur = cur.next;
        }
        return ans.next;
    }

    /** * 将从给定 head 节点开始的 k 个节点翻转 * @param head * @param k * @return */
    public ListNode reverse(ListNode head, int k) {
    
        // 当前翻转的长度
        int count = 1;
        // 上一个便利的节点
        ListNode last = head;
        // 当前遍历的
        ListNode cur = head.next;
        // 临时变量
        ListNode temp;
        // 若已翻转的长度不等于 k 时，继续翻转
        while (count != k) {
    
            // 当前翻转的长度 +1
            count++;
            // 存下要遍历的下个节点
            temp = cur.next;
            // 翻转
            // 将当前链表指针指向上一个节点
            cur.next = last;
            // 更新上一个遍历的节点
            last = cur;
            // 更新下一个遍历的节点
            cur = temp;
        }
        // newTail -> oldTail.next
        // head 即为翻转后的第 k 个节点，它的 next 要指向原来第 k 个节点的 next，也就是第 k + 1 个节点
        head.next = cur;
        // 返回翻转后的首节点
        return last;
    }