题解 | 链表中的节点每k个一组翻转

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        if (!head) return head; // 特判
        int cnt = 0;
        ListNode *cur = head;
        while (cur) {
            cur = cur->next;
            ++cnt;
        } // 计数
        if (cnt < k) return head; // 特判
        int round = cnt / k; // 轮次
        auto *new_H = new ListNode(0);
        new_H->next = head; cur = head;
        ListNode *pre = new_H, *start = pre;
        for (int i = 0; i < round; ++i) {
            int x = 0;
            while (x < k) {
                ListNode *tmp = cur->next;
                cur->next = pre;
                pre = cur;
                cur = tmp;
                ++x;
            }
            ListNode *tmp = start->next;
            start->next->next = cur;
            start->next = pre;
            start = tmp;
        }
        return new_H->next;
    }
};

题干分析:

题目要求我们对一个链表每k个节点一组,对每组节点进行反转操作后顺序连接,节点数不足k个的不反转.

算法思路:

注:由于题目要求最后一组不足k个节点便不反转,因此感觉有必要事先遍历一遍链表获取总节点数.个人解法也是通过这样做来保证正确性的,如果由只需遍历一次链表的解法欢迎补充.

具体算法逻辑见图:

开始:

反转第一组第一个节点

指针移动:

反转该组剩下节点

重新连接,并移动start指针(反转组开始指针):

开始反转下一组

重新连接与start指针移动:

按照图中的示例,此时已反转完毕,能够直接返回new_H->next了,如果后续还有分组,继续循环即可.

复杂度分析:

时间复杂度:遍历链表计数时间复杂度为O(n);对各个组别进行反转并连接,由于针对每个链表节点均需要进行一次操作,时间复杂度为O(n);其他操作时间复杂度为O(1).因此总时间复杂度仍为O(n).

空间复杂度:全过程只使用到了常数的额外空间,因此空间复杂度为O(1).