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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstddef>
class Solution {
 public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   *
   * @param head ListNode类
   * @param k int整型
   * @return ListNode类
   */

  pair<ListNode*, ListNode*> reversePart(ListNode* headNode, ListNode* tailNode) {
    ListNode* pre = new ListNode(-1);
    ListNode* cur = headNode;
    while (cur != tailNode) {
      ListNode* tmp = cur->next; //记录后面一个人
      cur->next = pre; //将当前人向后转
      pre = cur; // 更新前面一个人
      cur = tmp; // 更新当前人
    }
    cur->next = pre;
    return {cur, headNode};
  }
  ListNode* reverseKGroup(ListNode* head, int k) {
    // write code here
    if (head == NULL) {
      return nullptr;
    }
    ListNode* preInvNode = new ListNode(-2);
    preInvNode->next = head;
    ListNode* pre  = preInvNode;// 左边一棵树
    pre->next = head;
    ListNode* cur = pre;
    while (pre->next != NULL) {
      //寻找下一段链表的末端节点
      for (int i = 0; cur != NULL && i < k; i++) {
        cur = cur->next;
      }
      //如果链表的长度超过k, 则cur为第k个节点，否则cur = NULL.
      if (cur == nullptr) {
        return preInvNode->next;
      }
      //否则记录一下cur的下一个节点
      ListNode* cur_next  = cur->next;
      auto revheadtail = reversePart(pre->next, cur);
      pre->next = revheadtail.first;
      pre = revheadtail.second;
      pre->next = cur_next;
      cur = pre;
    }
    return preInvNode->next;
  }
};

思路是：遍历链表，每一次只翻转一段长为k的子链表。

只提交了两次就成功了，看来我确实是掌握了k个一组翻转链表的精髓，这是我通过努力记住了这个方法，为自己感到自豪。