Using recursion and chain header interpolation to realize the group turnover of linked lists -- leetcode25 K group turnover linked lists

Topic content

Give you the head node of the list head , Every time k Group of nodes to flip , Please return to the modified linked list .

k Is a positive integer , Its value is less than or equal to the length of the linked list . If the total number of nodes is not k Integer multiple , Please keep the last remaining nodes in the original order .

You can't just change the values inside the node , It's about actually switching nodes .

Example 1：

Input ：head = [1,2,3,4,5], k = 2
Output ：[2,1,4,3,5]

Example 2：

Input ：head = [1,2,3,4,5], k = 3
Output ：[3,2,1,4,5]

Tips ：
The number of nodes in the linked list is n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

Advanced ： You can design one that uses only O(1) Does the algorithm of extra memory space solve this problem ？

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/reverse-nodes-in-k-group
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

My solution

There are some similarities between the words of this question and the previous pairing Exchange , But the difference is that here we are k Flip them in groups .

For the flip of the linked list , I was really not very skilled at first , But after trying to draw a picture, I probably understood

We need three pointers , Two are used to record the flipped head and tail , A node used to calibrate a new plug .

We also need a marker , Tell the system when the turnover of a group is completed .

After finishing a group , Later, we can simply repeat this operation , It is worth noting that ,head Because of the principle of continuous plug , It just points to the head of the next group of nodes , So you can recurse directly .

Last run , I didn't expect the effect to be very good .

Implementation code

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution {
    
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
    
        ListNode* now=head;
        ListNode* l=head;
        for(int i=0;i<k;i++){
    
            if(now==nullptr){
    
                return head;
            }
            now=now->next;
        }
        // now=now->next;
        if(k==1){
    
            return head;
        }
        ListNode* biao=head->next;
        while(biao!=now){
    
            head->next=biao->next;
            biao->next=l;
            l=biao;
            if(head->next==now){
    
                break;
            }
            biao=head->next;
        }
        head->next=reverseKGroup(head->next,k);
        return biao;
    }
};

ps: The above is my explanation and code