题解 | #链表中的节点每k个一组翻转#
新设一个头结点方便操作，然后用三个指针pre,cur,tmp针对每k个元素进行一次反转，一轮反转之后更新pre为新的cur继续下一轮反转。
而反转的轮数需要根据结点总数来确定，所用先遍历一遍求出总结点数，除以k求出轮数。
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
if(head == NULL)
return NULL;
if(k == 1)
return head;
struct ListNode* result = malloc(sizeof(struct ListNode));
result->next = head;
struct ListNode *pre, *cur, *tmp;
pre = result, cur = head, tmp = NULL;
int len = 0;
while(head != NULL){
len++;
head = head->next;
}
int groups = len / k;
for(int i = 0; i < groups; i++){
for(int j = 1; j < k; j++){
tmp = cur->next;
cur->next = tmp->next;
tmp->next = pre->next;
pre->next = tmp;
}
pre = cur;
cur = cur->next;
}
return result->next;
上面的头插法是拆一个接一个，一直保持链表长度不变。
另一种更常规的头插法是新建一个头结点，然后从原链表每k个一反转，然后接入新链表，使新链表一节一节增长。
//第2种
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
if(head == NULL)
return NULL;
if(k == 1)
return head;
struct ListNode* c = head;
int len = 0;
while(c != NULL){
len++;
c = c->next;
}
int groups = len / k;
struct ListNode* result = malloc(sizeof(struct ListNode));
result->next = NULL;
struct ListNode* now;
now = result;
struct ListNode* hou;
for(int i = 0; i < groups; i++){
struct ListNode* tmp = malloc(sizeof(struct ListNode));
tmp->next = NULL;
for(int j = 0; j < k; j++){
hou = head->next;
head->next = tmp->next;
tmp->next = head;
head = hou;
}
now->next = tmp->next;
while(now->next != NULL)
now = now->next;
}
now->next = head;
return result->next;
}
查看1道真题和解析
加油！
智元机器人成长空间 243人发布