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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
  /*
  核心思想是 每k个元素看作是一个子链表，做该子链表的逆序，一共做 len/k次
  逆序的做法是 在头节点后面不断插入新遍历的节点
  */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        ListNode* p = head;
        int cnt = 0;
        struct ListNode* h = (struct ListNode*)malloc(sizeof(struct ListNode*));
        int len = 0;  //链表长度
        ListNode* q = head;
        while(q){
            len++, q= q->next;
        }
	  	// 记录每次 链表倒置时的最后一个位置
        ListNode* last = nullptr;
	  // 记录每次 链表倒置
        ListNode* lastn = nullptr;
        int times = 0;
        int m = len / k;
        while (p) {
            printf("p=%d\n", p->val);
            ListNode* n = p->next;
            if (times == 0) {
                if (cnt == 0) {
                    last = p;
                    p->next = nullptr;
                } else {
                    p->next = h->next;
                }
                h->next = p;
                cnt++;
                if (cnt == k) {
                    cnt = 0;
                    times ++;
                }
            }else{
                if (cnt == 0) {
                    lastn = p;
                    p->next = nullptr;
                } else {
                    p->next = last->next;
                }
                last->next = p;
                cnt++;
                if (cnt == k){
                    cnt = 0, times++;
                    last = lastn;
                }
            }
            p = n;
            if(times==m){
                last->next = p;
                break;
            }
        }
        return h->next;


    }
};