LeetCode 25：K个一组翻转链表

题目

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

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

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

示例1

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例2

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

示例3

输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]

示例4

输入：head = [1], k = 1
输出：[1]

思路

主要分为两步：

• 首先判断节点是否够k个，若不到k个直接返回(break)
• k个节点翻转：
  • 如0->1->2->3->4，假设k=3，翻转1->2->3，先让该k节点内部翻转1<-2<-3然后让0->3，最后再让1->4，从而形成0->3->2->1->4，形成翻转

时间复杂度分析：O(n)，对链表进行遍历一次O(n)，还有两次遍历都是常量空间O(k)

c++代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution {
    
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
    
        auto dummy = new ListNode(-1);
        dummy->next = head;
        for (auto p = dummy; ; ) {
    
            auto q = p;
            /** 判断该点之后是否有k个元素 */
            for (int i = 0; i < k && q; i ++) q = q->next;
            if (!q) break;  /* 不足k个元素直接返回 */
            auto a = p->next, b = a->next;
            for (int i = 0; i < k - 1; i ++) {
    
                auto c = b->next;
                b->next = a;
                a = b, b = c;
            }
            auto c = p->next;
            p->next = a, c->next = b;
            p = c;
        }
        return dummy->next;
    }
};