题目

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

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

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

示例：

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

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

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

说明：

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

题目链接

题目分析

基本的思路就是根据k来逐步翻转链表。

为了方便操作，给原始链表添加头结点，然后遍历一次链表，获得链表长度，利用链表长度计算迭代次数。

int len = 0;
while (head){
    len++;
    head = head->next;
}
int it = len / k;

然后需要实现链表部分翻转，假设这个链表的起始结点的前驱结点是pre，首结点为cur，需翻转k个元素：

for (int i = 1; i < k; i++){
    list next = cur->next;
    cur->next = next->next;
    next->next = pre->next;
    pre->next = next;
}
pre = cur;
cur = pre->next;

找一组数字来验证上述过程，链表0->1->2->3->4->5，我们需要翻转1 2 3，pre = 0, cur = 1:

• 第一步，next = 2, cur->next = 3(1->3),next->next = 1(2->1),pre->next = 2(0->2),局部链表变为：0->2->1->3
• 第二步，next = 3, cur->next = 4(1->4),next->next = 2(3->2),pre->next = 3(0->3),局部链表变为：0->3->2->1
• 局部变换完成。

题目解答

typedef struct ListNode* list;

struct ListNode* reverseKGroup(struct ListNode* head, int k){
    list dummy = (list)malloc(sizeof(struct ListNode));
    dummy->next = head;
    list pre = dummy;
    list cur = pre->next;

    int len = 0;
    while (head){
        head = head->next;
        len++;
    }

    int it = len / k;
    while (it--){
        for (int i = 1; i < k; i++){
            list next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        pre = cur;
        cur = pre->next;
    }

    return dummy->next;
}