题解 | #看不懂递归写法,直接在链表上进行分组逆置#
链表中的节点每k个一组翻转
https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ 每k个一组翻转,那么翻转多少次进能使用链表的长度/k来得到 翻转的方式采用的是头插,即题目 BM2 链表内指定区间反转 中的方式,建议先做这个题目,再来看这道题 这题翻转的时候,我们就是采用和上面那到题目一样的方式--头插。 k=2的时候,我们只需要头插1次 k=3的时候,头插2次 即头插的次数也是由K决定的,即1次 分组看待每次要翻转的部分,完成一次翻转之后,就更新pre和cur的位置,以方便进行下一次的翻转。 class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { int count = 0;//链表的长度 ListNode* phead = new ListNode(0);//头结点 phead->next = head; ListNode* pre = phead;//cur的前一个指针 ListNode* cur = head; while(cur != nullptr) { count++; cur = cur->next; } int n = count / k;//反转的组数 cur = head;//计算完count之后,让cur重新来到head的位置,上面仅仅是为了计算count才使用的cur,也可以再定义一个指针用来计算链表的长度(count) for(int i = 0; i < n; ++i)//总共反转多少组 { //进行反转 for(int f = 1; f < k; ++f)//要进行k-1次头插 { ListNode* temp = cur->next; cur->next = temp->next; temp->next = pre->next; pre->next = temp; } //更新pre和cur以便下一次进行头插 pre = cur; cur = cur->next; } //返回的头结点的下一个 return phead->next; } };