25. k个一组翻转链表

1. 题目描述2.代码如下

原题目连接

1. 题目描述

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

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

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

2.代码如下

//2018-12-06 思路：头插法，每插一段就移动一段，保证“头”一直在最后面 struct ListNode* reverseKGroup(struct ListNode* head, int k) { if(k==1||!head||!head->next) { return head; } typedef struct ListNode list; list* new_head=malloc(sizeof(list)); list* preal = new_head; list* pnext; new_head->next = NULL; list* p=head; int len=0; while(p) { len++; p = p->next; } if(len<k) { return head; } int count = len/k;//求得需要头插的段数 p = head; pnext = p->next; int i =0; while(i<count) { int j = 0; while(j<k&&p) { p->next = new_head->next; new_head->next = p; if(pnext)//非常重要的边界条件 { p = pnext; pnext = pnext->next; } else { return preal->next; } j++; } int l = k; while(l) { new_head = new_head->next; l--; } i++; } //k<len的情况下，头插后还剩一个字段长度<k的链表，要将它接上 list *ptemp=preal->next; while(ptemp->next!=NULL) { ptemp = ptemp->next; } ptemp->next = p; return preal->next; } ```c