题解 | #链表中的节点每k个一组翻转#

一、解题思路

把链表每k个分成一组，然后反转这每一组的节点，接着在把他们串起来即可

注意点:

1. 每k个一组将链表的最后一个节点指向nullptr标记为为断点，方便进行反转
2. 经过反转之后，k个节点的初始节点反转到链表的尾部了，就是已经反转之后的尾结点了，让它指向下一次反转的头结点即可

二、代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     * 算法思想:把链表每k个分成一组，然后反转这每一组的节点，接着在把他们串起来即可。
     */

     ListNode* reverse(ListNode* head) {
        ListNode *pre=nullptr,*cur=head;
        while(cur!=nullptr) {
            ListNode* temp_node=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp_node;
        }
        return pre;
     }
    ListNode* reverseKGroup(ListNode* head, int k) {
        //创建一个哑节点
        ListNode* dummy = new ListNode(0);
        //让哑节点的头指向链表的头
        dummy->next = head;
        //开始反转的前一个节点，比如反转的节点范围是[link1，link2]，那么pre就是link1的前一个节点，end就是link2
        ListNode* pre = dummy;
        ListNode* end = dummy;
        while(end->next!=nullptr) {
            //每k个反转，end为每组链表的最后一个
            int count = 1;
            while(count<=k&&end!=nullptr) {
                end=end->next;
                count++;
            }
            //如果end是空，说明不够k个，就不需要反转了，直接退出循环。
            if(end==nullptr) {
                break;
            }
            //反转开始的节点
            ListNode* start = pre->next;
            //next为下一次反转开始的节点，先记录下来
            ListNode* next = end->next;
            //将需要反转的链表的最后一个节点的指向置为nullptr，方便进行反转
            end->next=nullptr;
            //反转之后，让pre的指针指向这个反转的小链表
            pre->next=reverse(start);
            //注意经过上一步反转之后，start反转到链表的尾部了，就是已经反转之后的尾结点了，让它指向下一次反转的头结点即可（上面分析过，next就是下一次反转的头结点）
            start->next=next;
            pre=start;
            end=start;
        }
        return dummy->next;
    }
};