C language force buckle question 25 of K a group of inverted linked list. Multi pointer traversal

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 .

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

The linked list partition is the flipped part + The part to be flipped + Non flipped part
Before each flip , To determine the scope of flipping the linked list , This must pass k This loop determines
It is necessary to record the precursor and successor of the flipped linked list , It is convenient to connect the flipped part and the non flipped part after flipping
Two variables are required initially pre and end,pre Represents the precursor of the linked list to be flipped ,end Represents the end of the linked list to be flipped
after k This cycle ,end To the end , Record the successor of the linked list to be flipped next = end.next
Flip list , Then connect the three parts of the linked list , Then reset pre and end The pointer , Then go to the next cycle
A special case , When the length of the flipped part is insufficient k when , In positioning end After completion ,end==null, We've reached the end , Explain that the topic has been completed , Just go back

In fact, this problem is to reverse the entire linked list many times , Please refer to my other blog to reverse the whole linked list C Language power deduction 206 Reverse linked list . Double finger needling , Iterative recursion （ Three methods ）. Graphic nanny tutorial _ Take care of two dogs and never put a bad blog -CSDN Blog

struct ListNode* reverseKGroup(struct ListNode* head, int k){
    struct ListNode *dummy = malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode *node = head;
    struct ListNode *sectionNext = NULL,*tail = NULL;
    struct ListNode *sectionPrev = dummy;
    int actualLength = 0;
    while(node != NULL){
        actualLength = 0;
        /*1.  Statistics k A length of node,tail Point to the end of the paragraph ,node Out of the current period , Point to the next paragraph */
        while(node != NULL && actualLength<k){
            tail = node;
            node = node->next;
            actualLength++;
        }
        sectionNext = node;  // The next paragraph points to the paragraph 
        if(actualLength==k){ // It indicates that the current length is k  Out of circulation  , It doesn't matter node Is it empty ,node Is the beginning of the next paragraph , As long as the length reaches, it can be reversed  , Start reverse 
            struct ListNode *prev = NULL,*next = NULL;  // classical 3 Pointer reversal 
            node = sectionPrev->next;   //node  Go back to the beginning of the current paragraph 
            tail = node;            // meanwhile tail  Come back, too 
            prev = sectionNext;  //prev  Point to the beginning of the next paragraph , After the list is reversed, the tail points to the beginning of the next paragraph 
            while(sectionNext != node){  //while The loop condition  node  It hasn't shifted to the beginning of the next paragraph 
                /*prev curnode  next  Three pointer inversion method */
                next = node->next; 
                node->next = prev;
                prev = node;
                node = next;
            }
            /* After successful inversion ,prev Namely   The chain header of the current segment */
            sectionPrev->next = prev;  // In the previous paragraph next The chain header pointing to the current segment 
        }
        /* The next cycle */
        sectionPrev = tail;  //sectionprev Point to the tail of the current segment , As the front node of the next section 
        node = sectionNext;  //node  Point to the beginning of the next paragraph 

    }
    return dummy->next;  // Return to sentinel node 
}

In addition, the following method can not be used to display the access null pointer all the time , But you can live VS

struct ListNode* reverseKGroup(struct ListNode* head, int k)
{
	struct ListNode* tail = head;
	struct ListNode* cur = NULL;
	struct ListNode* pre = head;
	struct ListNode* head1 = NULL;
	struct ListNode* head2 = head;
	int i = 0;
	for (i = 0; i < k-1; i++)
	{
		if (tail->next == NULL)
			return head;
		tail = tail->next;
	}
	head1 = tail;
	while (1)
	{
		head2 = head;
		for (i = 0; i < k-2; i++)
		{
			head = head->next;
			cur = head->next;
			head->next = pre;
			pre = head;
		}
		head = cur;
		if(tail->next==NULL)
		{ 
			head->next = pre;
			head2->next = NULL;
			return head;
		}
		else
		{
			cur = tail->next;
			if (pre == NULL)
				return;
			head->next = pre;
			head = cur;
			pre = head;
			tail = head;
		}
		for (i = 0; i < k-1; i++)
		{
			if (tail->next == NULL)
				break;
			tail = tail->next;
		}
		if (i != k - 1)
		{
			head2->next = cur;
			break;
		}
		else
			head2->next = tail;
	}

	head = head1;
	return head;
}