25.k-个一组翻转链表.md

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
  // 翻转一个子链表，并且返回新的头与尾
  pair<ListNode *, ListNode *> myReverse(ListNode *head, ListNode *tail) {
    ListNode *cur = head;
    ListNode *pre = nullptr;
    // 和模板的反转链表不同，这里通过pre!=tail结束，而非while(cur)结束
    while (pre != tail) {
      ListNode *tmp = cur->next;
      cur->next = pre;
      pre = cur;
      cur = tmp;
    }
    return {tail, head};
  }

  ListNode *reverseKGroup(ListNode *head, int k) {
    // 创建虚拟头节点
    ListNode *dummy = new ListNode(0);
    dummy->next = head;
    ListNode *pre = dummy;

    while (head) {
      ListNode *tail = pre;
      // 移动tail到子链表的末尾
      for (int i = 0; i < k; ++i) {
        tail = tail->next;
        // 如果该过程tail为空，表示剩下的部分，无需再反转
        if (!tail) {
          return dummy->next;
        }
      }
      // 提前记录临时tmp，子链表的下一个node
      ListNode *tmp = tail->next;
      // 反转子链表，将head、tail重新指向反转后的头尾
      // 如1(head)>2(tail)，变为2(head)>1(tail)
      tie(head, tail) = myReverse(head, tail);
      // 把子链表重新接回原链表(前后各自连接)
      pre->next = head;
      tail->next = tmp;
      // pre移动到tail处
      pre = tail;
      // head移动到tmp处
      head = tmp;
    }

    return dummy->next;
  }
};