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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *tail = head;
        for (int i = 0; i < k; i++) {
            // 如果不足k就到了链表尾部,则直接返回,不用对该区间进行翻转
            if (tail == nullptr) {
                return head;
            }
            tail = tail->next;
        }
        ListNode *pre = nullptr;
        ListNode *cur = head;
        while (cur != tail) {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        // 将区间翻转后的尾部,指向下一段要翻转的区间
        head->next = reverseKGroup(tail, k);
        return pre; // 返回区间翻转后的头部
    }
};

基本思路:

  • 使用递归处理每个 k 区间内的链表
  • 每次的递归处理结果
  • 如果需要翻转则进行翻转,如果不需要则直接返回该区间的 head
  • 区间翻转后,将尾部指向下一段要处理的区间
  • 最后返回翻转后区间的头部