题目描述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

样例

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

算法1

(迭代模拟) $O(n)$

链表模拟题，没啥特殊技巧，画图，仔细模拟。

时间复杂度

遍历整个链表，时间复杂度是$O(n)$

参考文献

C++ 代码

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || !head->next) return head;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *pre = dummy, *cur = dummy, *post = nullptr;
        while (true){
            bool flag = false;
            for (int i = 0; i < k; ++i){
                if (!cur->next){
                    flag = true;
                    break;
                }
                cur = cur->next;
            }
            if (flag) break;

            post = cur->next;
            cur->next = nullptr;

            ListNode *tail = pre->next;
            reverseList(tail);
            pre->next = cur;
            tail->next = post;

            pre = cur = tail;
        }

        pre = dummy->next;
        delete dummy; dummy = nullptr;
        return pre;
    }

    void reverseList(ListNode *head){
        if (!head || !head->next) return;
        ListNode *pre = nullptr, *cur = head, *post = nullptr;

        while (cur){
            post = cur->next;
            cur->next = pre;
            pre = cur;
            cur = post;
        }
    }

算法2

(递归) $O(n)$

迭代模拟非常麻烦，可以递归求解。

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || !head->next) return head;
        ListNode *p = head;
        for (int i = 0; i < k - 1; ++i){
            if (!p->next){
                return head;
            }
            p = p->next;
        }

        ListNode *node = reverseKGroup(p->next, k);
        p->next = nullptr;
        reverseList(head);

        head->next = node;
        return p;
    }

    void reverseList(ListNode *head){
        if (!head || !head->next) return;
        reverseList(head->next);
        head->next->next = head;
    }
};