46-K个一组翻转链表

自己的做法

算法思想

首先遍历链表获得链表长度size。size / k = n，n就是需要翻转的链表的个数。

因为如果size不是k的整数倍，那么最后剩余的节点不需要翻转。

所以只需要关注前面n个链表即可。

首先要写一个反转函数。

参数：链表头节点。

返回值：包含两个节点指针，第一个是反转后的链表头指针，第二个是反转后的链表尾指针。

因为反转后的链表需要拼接回原链表，所以需要两个指针。当然也可以只返回 反转后的链表头节点，然后遍历该链表找到链表尾指针，但会增加程序执行次数，增加时间复杂度。

添加哑节点dummy，设置pre指针为待反转的链表头节点的前一个节点，初始pre指向dummy。

cur指针初始指向pre，向后走k步，刚好到达待反转链表的尾部，记录下尾节点的下一个节点next，以便于反转后拼接。

然后断开，即cur->next = nullptr。

反转后链表为reversed,进行拼接，pre指向reversed头节点，reversed尾节点指向next。

然后将pre指向reversed尾节点。

循环n次，即可完成反转。

算法实现

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        int size = 0;
        ListNode * node = head;
        while (node) {
            size++;
            node = node->next;
        }
        int n = size / k;
        ListNode * dummy = new ListNode();
        dummy->next = head;
        ListNode * pre = dummy;
        for(int i = 0; i < n; i++) {
            ListNode * cur = pre;
            for(int j = 0; j < k; j++) {
                cur = cur->next;
            }
            ListNode * next = cur->next;
            cur->next = nullptr;
            pair<ListNode *, ListNode *> reversed = reverse(pre->next);
            pre->next = reversed.first;
            reversed.second->next = next;
            pre = reversed.second;
        }
        return dummy->next;
    }

     pair<ListNode *, ListNode *> reverse(ListNode * head) {
        if(head == nullptr || head->next == nullptr) {
            return make_pair(head, head);
        }
        ListNode * pre = nullptr, * cur = head;
        while (cur != nullptr) {
            ListNode * next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return make_pair(pre, head);
    }
};

性能分析

时间复杂度：一共进行了 size / k次反转，每次反转的链表长度都为k。先找到待反转链表的尾节点，k次操作，再进行反转，还是k次操作。所以共执行了 2 * size次操作。开头遍历链表获取长度。所以时间复杂度为$O(n)$，n为链表长度。

空间复杂度：$O(1)$。

改进

可以不获得链表长度，而是每次走k步，如果当前指向节点为空，代表这段链表长度小于k，即为最后一段剩余链表，直接返回即可。

使用head当做遍历指针。

算法实现

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode * dummy = new ListNode();
        dummy->next = head;
        ListNode * pre = dummy;
        while(head) {
            for(int j = 1; j < k; j++) {
                head = head->next;
                if(head == nullptr) {
                    return dummy->next;
                }
            }
            ListNode * next = head->next;
            head->next = nullptr;
            pair<ListNode *, ListNode *> reversed = reverse(pre->next);
            pre->next = reversed.first;
            reversed.second->next = next;
            pre = reversed.second;
            head = next;
        }
        return dummy->next;
    }

     pair<ListNode *, ListNode *> reverse(ListNode * head) {
        if(head == nullptr || head->next == nullptr) {
            return make_pair(head, head);
        }
        ListNode * pre = nullptr, * cur = head;
        while (cur != nullptr) {
            ListNode * next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return make_pair(pre, head);
    }
};

性能分析

同上。

参考做法相同。