题解 | #链表中的节点每k个一组翻转#

最简单的思路：先遍历一次，再按组翻转，时间复杂度还是O(N)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
      if (head == nullptr || head->next == nullptr || k == 1) { // 不需要翻转
        return head;
      }
      
      auto head_node = new ListNode(-1);
      head_node->next = head;
      
      auto count_ptr = head;
      auto len = 0;
      
      while (count_ptr) {
        ++len;
        count_ptr = count_ptr->next;
      }
      
      auto num_of_groud = len / k;
      auto pre = head;
      auto cur = pre->next;
      auto nex = cur->next;
      auto start_of_groud = pre;
      auto end_of_pre_groud = head_node;
      
      while (--num_of_groud >= 0) {  // 按组处理
        for (int i = 1; i < k - 1; i++) { // cur最后指向一组的尾结点
          cur->next = pre;
          pre = cur;
          cur = nex;
          nex = nex->next;
        }
        // 连接前后组
        cur->next = pre;
        end_of_pre_groud->next = cur;
        start_of_groud->next = nex;
        
        if (num_of_groud == 0) {
          break;
        }
        
        // 更新
        end_of_pre_groud = start_of_groud;
        start_of_groud = nex;
        pre = cur = nex;
        cur = pre->next;
        nex = cur->next;
      }
      
      head = head_node->next;
      delete(head_node);
      return head;
    }
};