LeetCodeK 个一组翻转链表——C

水深无声 2023-06-16 04:00 3阅读 0赞

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group

## 一、题目描述 ##

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。  
k 是一个正整数，它的值小于或等于链表的长度。  
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :
    给定这个链表：1->2->3->4->5
    当 k = 2 时，应当返回: 2->1->4->3->5
    当 k = 3 时，应当返回: 3->2->1->4->5

说明 :  
你的算法只能使用常数的额外空间。  
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

## 二、题解 ##

每次规划出要翻转的 k 个节点，然后把这一组翻转，拼接到返回的链表后面，剩余部分不足三个的直接拼接链表后面。

struct ListNode* reverse(struct ListNode* head) {
        
    	struct ListNode* pre = NULL;				//定义一个节点 
    	struct ListNode* curr = head;				//curr 表示链表 
    	while (curr != NULL) {
        
    		struct ListNode* next = curr->next;		//记录洗一个节点
    
    		curr->next = pre;						//当前节点连接到 pre 前面
    		pre = curr;								//pre 向前移动
    		
    		curr = next;							//curr 指向下一个节点
    	}
    	return pre;	
    }
    
    struct ListNode* reverseKGroup(struct ListNode* head, int k) {
        
    	struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    	dummy->next = head;
    	struct ListNode* pre = dummy;				//记录前驱节点 
    	struct ListNode* post = dummy;				//记录后继节点 
    
    	while (post->next != NULL) {
        
    		for (int i = 0; i < k && post != NULL; i++) {
        
    			post = post->next;					//后继节点向后移动 k 位 
    		}
    		if (post == NULL) {
        						//跳出循环，最后剩余的节点保持原有顺序 
    			break;
    		}
    		struct ListNode* start = pre->next;		//开始节点是前驱节点 
    		struct ListNode* next = post->next;		//记录下一个开始节点 
    		post->next = NULL;						//把 k 个节点封装成一个链表 
    		pre->next = reverse(start);				//反转这 k 个节点的链表，并连到 pre 后面
    		
    		start->next = next;						//下一次开始节点
    		pre = start;							//下一次前驱节点 
    		post = start;							//下一次后继节点 
    	}
    	return dummy->next;
    }

## 三、调试 ##

#include<stdio.h>
    #include<malloc.h>
    
    struct ListNode {
        
    	int val;
    	struct ListNode* next;
    };
    
    //尾插法
    void CreateListR(struct ListNode*& L, int array[], int n) {
        
    	struct ListNode* s, * r;
    	L = (struct ListNode*)malloc(sizeof(struct ListNode));	//创建头结点
    	r = L;										//r 始终指向尾结点，初始时指向头结点 （头结点序号为 0） 
    	for (int i = 0; i < n; i++) {
        				//循环建立数据节点 s
    		s = (struct ListNode*)malloc(sizeof(struct ListNode));
    		s->val = array[i];						//赋值 
    		r->next = s;							//将结点 s 插入到结点 r 之后 
    		r = s;
    	}
    	r->next = NULL;								//尾结点其 next 域置为 NULL 
    }
    
    //输出线性表
    void Display(ListNode* L) {
        
    	ListNode* p = L;							//p 指向首结点 （首结点序号为 1） 
    	while (p != NULL) {
        							//不为空，依次遍历 
    		printf("%d ", p->val);
    		p = p->next;							//p 移向下一个节点 
    	}
    	printf("\n");
    }
    
    struct ListNode* reverse(struct ListNode* head) {
        
    }
    
    struct ListNode* reverseKGroup(struct ListNode* head, int k) {
        
    }
    
    int main() {
        
    	struct ListNode* L = (struct ListNode*)malloc(sizeof(struct ListNode));
    	int array[] = {
         1,2,3,4,5 };
    	int n = sizeof(array) / sizeof(array[0]);
    	int k = 3;
    	CreateListR(L, array, n);
    	Display(L->next);
    	struct ListNode* reverseK = reverseKGroup(L->next, k);
    	Display(reverseK);
    	return 0;
    }

## 四、结果 ##

**1、控制台输出**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

**2、LeetCode**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019112414171476.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191124141804109.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70