K个一组链表翻转

目录

1. 题意

2. 解题思路

3. 代码

---

1. 题意

给一个链表，按 k 进行翻转，也就是 k = 2 ，两两进行翻转，如果不够2则不动。

2. 解题思路

首先思考怎么翻转一个链表，反转链表：https://leetcode.cn/problems/UHnkqh/description/

只要最开始记录1和2，2个节点，并让1指向空，在根据2得到3节点。

根据题意说明反转k次，那么首先计算总共要反转多少次，比如：

总共5个节点，5/2，总共反转2次，结束让最后的指针指向剩余的节点。

那么知道怎么反转了，那怎么得到答案呢？

首先反转1和2 

2作为起点，怎么存？很好解决让new一个指针ans，定义一个指针tmp=ans指向他，那怎么让反转后的最后一个节点1指向下一个节点？很好解决，因为最开始的时候cur已经指向1了，直接存。

最开始的状态直接标记cur，用一个pos指针标记

反转后的状态直接让tmp指向他，也就是 ans的next 指向 prev 所在的位置并让 tmp进行指向(ans后续返回答案要用)。

然后让tmp指向之前标记的cur也就是pos，也就是反转之前的头部。

进行第二次反转：

先让pos=cur进行标记反转前的头部

然后进行反转

让tmp指向prev

在让tmp等于pos，和第一次步骤一样。

结束，让tmp指向没反转的节点，节点就是cur指向的节点。

3. 代码

    int Licount(ListNode* head){   int cnt=0;while(head){++cnt;head=head->next;}return cnt;}ListNode* reverseKGroup(ListNode* head, int k) {// 求链表长度int cnt = Licount(head);// 求总共反转多少次cnt/=k; // 让这个新的节点指向最终答案ListNode* tmp=new ListNode(-1);// 让这个链节点把 2个反转之后的链表 进行衔接ListNode* tmp_next=tmp;// 进行反转定义的3个指针ListNode* prev=nullptr,*mid=head,*tail=head->next;while(cnt--){// 保存要反转的 链表的最开始的头部ListNode* pos=mid;// 反转k次for(int i=0;i<k;++i){mid->next=prev;prev=mid;mid=tail;if(tail!=nullptr)tail=tail->next;}// 让tmp 指向反转后的链表的头部tmp_next->next=prev;// 让tmp等于链表最开始的头部，反转前的头部tmp_next=pos;// 让他指向空，不执行也没问题tmp_next->next=nullptr;}// 衔接没参与反转的链表tmp_next->next=mid;// 返回最后的答案return tmp->next;}