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

1. 题目考察的知识点

链表的反转操作

2. 题目解答方法的文字分析

通过链表长度len和K值确定需要反转的结点数,即len/k为要反转的组数，(len/k)*k为要反转的节点数，剩下的就是不需要翻转，直接链接到新链表末尾即可。 每K个反转成新链表，把每个新链表的head保存到List中.需要反转的结点数已到并且剩下的结点数不足K个，不反转，即把当前结点存到List中。最后把List中各个链表连接形成答案。

3. 本题解析所用的编程语言

java

4. 完整且正确的编程代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        if (head == null || k == 1) {
            return head;
        }

        ListNode p = head;
        //获取链表长度
        int len = 0;
        while (p != null) {
            len++;
            p = p.next;
        }

        ListNode reverseListHead = null;
        ListNode curNode = head;
        ListNode preNode = null;
        ListNode nextNode = null;
        //List存放各链表头结点
        List<ListNode> list = new ArrayList<ListNode>();

        //count 计数器 记录k个元素，每k个重新置1
        int count = 1;
        //需要发生反转的结点个数
        int reverseNum = (len / k) * k;
        while (curNode != null) {

            nextNode = curNode.next;

            if ( count <= k) {

                if (count == k) {

                    reverseListHead = curNode;
                    list.add(reverseListHead);
                    count = 1;

                    curNode.next = preNode;
                    preNode = null;
                    curNode = nextNode;
                } else {
                    count++;

                    curNode.next = preNode;
                    preNode = curNode;
                    curNode = nextNode;
                }
            }

            if (reverseNum == 1 && count != k) {
                list.add(curNode);
                break;
            }

            reverseNum--;

        }
        ListNode newHead = list.get(0);

        for (int i = 0; i < list.size() - 1; i++) {
            p = list.get(i);
            while (p.next != null) {
                p = p.next;
            }
            p.next = list.get(i + 1);

        }

        return newHead;

    }
}