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

yunshengd / 2023-05-04 / 原文

描述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

数据范围：

例如：

给定的链表是

对于

step 1：每次从进入函数的头节点优先遍历链表k次，分出一组，若是后续不足k个节点，不用反转直接返回头。

step 2：从进入函数的头节点开始，依次反转接下来的一组链表，反转过程同反转链表的题目。

step 3：这一组经过反转后，原来的头变成了尾，后面接下一组的反转结果，下一组采用上述递归继续。

具体过程如下图（k=3为例）：

递归过程

回溯过程

最底层返回的是第一个分组的pre,也就是新链表的头结点。

代码

 1 /**
 2  * struct ListNode {
 3  *    int val;
 4  *    struct ListNode *next;
 5  * };
 6  */
 7 
 8 #include <cstddef>
 9 class Solution {
10 public:
11     /**
12      * 
13      * @param head ListNode类 
14      * @param k int整型 
15      * @return ListNode类
16      */
17     ListNode* reverseKGroup(ListNode* head, int k) {
18         ListNode *tail=head;
19         //遍历k次
20         for(int i=0;i<k;i++){
21             if(tail==nullptr) return head;
22             tail=tail->next;
23         }
24         //反转当前段
25         ListNode *pre=nullptr;
26         ListNode* cur=head;
27         while(cur!=tail){
28             ListNode* temp=cur->next;
29             cur->next=pre;
30             pre=cur;
31             cur=temp;
32         }
33         //递归
34         head->next=reverseKGroup(tail,k);
35         //返回当前段的pre,用来连接前一段的链表
36         return pre;
37     }
38 };