思路

想了两节课终于想出来了

在此之前我们先复习一下反转链表

[206.反转链表 | ᕙ(• ॒ ູ•)ᕘ欢迎光临ᕙ(`▿´)ᕗ](https://cotton-star.github.io/2024/11/04/leedcode刷题之旅/206. 反转链表/)

  • 我们需要一个哑结点p,一组的开头start,一组的结尾end,以及下一组的开头k

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL){
        return 0;
    }
    struct ListNode* pre=NULL;
    struct ListNode* curr=head;
    struct ListNode* temp=NULL;
    while(curr!=NULL){
        temp=curr->next;
        curr->next=pre;
        pre=curr;
        curr=temp;
    }
    return pre;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    struct ListNode* dummy=malloc(sizeof(struct ListNode));
    dummy->next=head;
    struct ListNode* end = dummy;
    struct ListNode* pre = dummy;
    while(end->next!=NULL){
        for(int i=0;i<k&&end!=NULL;i++){
            end=end->next;
        }
        if(end==NULL){
            break;
        }
        struct ListNode* s=pre->next;
        struct ListNode* k=end->next;
        end->next=NULL;
        pre->next=reverseList(s);
        s->next=k;
        pre=s;
        end=s;
    }
    return dummy->next;
}