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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param k int整型
 * @return ListNode类
 */
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* prev = &dummy, *curr = head;
    int count = 0;

    // Count the number of nodes in the list
    while (head) {
        count++;
        head = head->next;
    }

    while (count >= k) {
        struct ListNode* start = prev->next;
        struct ListNode* nex = curr->next;

        for (int i = 1; i < k; i++) {
            curr->next = nex->next;
            nex->next = prev->next;
            prev->next = nex;
            nex = curr->next;
        }

        prev = start;
        curr = start->next;
        count -= k;
    }

    return dummy.next;
}

长度为n的链表反转就是：

    让当前第二个节点排在当前第一个节点前面；

    让当前第三个节点排在当前第一个节点前面；

    ......

    一直把n个都排完

例如：

    12345

    21345

    32145

    43215

    54321

每次需要操作的有三个节点：

    当前第n个节点：第n个节点的next指向第一个节点；

    当前第1个节点：因为每次第1个节点都在变，所以声明头节点；

    当前第n-1个节点：第n-1个节点指向第n+1个节点；