代码:
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* @author Senky
* @date 2023.03.23
* @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
*/
/**
* @brief reverse a list
* @param pHead ListNode类
* @return ListNode类
*/
struct ListNode* ReverseList(struct ListNode* pHead ) {
struct ListNode* prev = NULL;
struct ListNode* curr = pHead;
struct ListNode* next;
//退出循环后curr指向NULL
while(curr != NULL)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
// write code here
struct ListNode* reversehead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* reversetail = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* reversehead_front = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* reversetail_next = (struct ListNode*)malloc(sizeof(struct ListNode));
reversehead = head;
reversehead_front = NULL;
reversetail = head;
/*reversetail_next始终指向reversetail的下一个结点*/
reversetail_next = reversetail->next;
/*初次翻转标记*/
int firstreverse = 1;
/*当前链表的尾结点的下一个不为空说明还要继续翻转*/
while(reversetail != NULL)
{
/*找到反转链表的尾结点*/
for(int reversenum = 1; reversenum < k; reversenum++)
{
if(reversetail->next != NULL)
{
reversetail = reversetail->next;
}
else
{
return head;
}
}
if(reversetail->next != NULL)
{
reversetail_next = reversetail->next;
}
else
{
reversetail_next = NULL;
}
if(reversetail != NULL)
{
reversetail->next = NULL;
if(1 == firstreverse)
{
/*初次翻转需要改变head指向*/
head = ReverseList(reversehead);
firstreverse = 0;
}
else
{
/*链接翻转链表头部*/
reversehead_front->next = ReverseList(reversehead);
}
reversehead_front = reversehead;//下一个循环的reversehead_front指向本次循环的reversehead
reversehead->next = reversetail_next;//链接翻转链表尾部
/*指针指向下一个翻转链表的头结点*/
reversehead = reversetail_next;
reversetail = reversetail_next;
}
}
return head;
}
图解:


注:malloc的指针记得free掉