241763e249634a51ad3b5a21504cd2d0.png

【题目】：25. K 个一组翻转链表

while(cur && kk--)

分类讨论：退出循环有两种情况，

  1. kk == 0：此时说明仍然有k个元素可以进行反转，可以直接将反转后的结果和尾部相连
  2. cur == nullptr：此时如果kk > 0，说明链表中已经不足k个了，此时不应该反转，但是我之前已经将链表反转过了，所以需要再进行二次反转。这样最多只需要再遍历k-1次，比事先判断是否满足k个再进行反转的效率相对也会高点。
class Solution {
public:
    ListNode* reverse(ListNode* head) {
        ListNode* res = nullptr, *cur = head;
        while(cur) {
            ListNode* temp = cur->next;
            cur->next = res;
            res = cur;
            cur = temp;
        }
        return res;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* res = new ListNode();
        ListNode* tail = res;
        ListNode* cur = head;
        while(cur) {
            ListNode* tailTemp = cur; // 反转前的头节点
            // 反转k个
            int kk = k;
            ListNode* reverseHead = nullptr;
            // 反转
            while(cur && kk--) {
                ListNode* temp = cur->next;
                cur->next = reverseHead;
                reverseHead = cur;
                cur = temp;
            }
            if(kk > 0) {
                // 二次反转reverseHead后再接到尾部（不足k个）
                tail->next = reverse(reverseHead);
            }else {
                // 直接把反转的接到尾部（k个）
                tail->next = reverseHead;
            }
            tail = tailTemp; // 更新尾部（反转之前的头部就是tail）
        }
        return res->next;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

这题的难点在于：

  1. 如果最后不足k个要怎么处理？可以进行二次反转
  2. res链表的尾部怎么更新？res链表的尾部，相当于反转前那个链表的头部（在反转前需要提前记录）