与反转题目基本相同,这里的难点就是找范围,在范围里进行交换。
准备工作:cur1,cur2定义出来,用来保存要反转的范围。当然还要有一个prev指针记录cur1前一个的指针。
找范围:cur2往后走k-1个,找到最右边的范围,这样我们就有了一组的反转目标。
反转:参考上一题的思路,分两个情况,一个是head要参与交换的,一个不是head交换
反复k反转的循环。这样我们要在我们在嵌套一层循环,通过调试我其实发现我这个反转函数的cur2变成了原来的cur1,所有我又重新让cur2往后面走了k-1次,然后保存prev为cur2,cur1指向cur2的下一个。这个循环的结束为cur2的下一个是不是空指针。(我感觉这段代码有很多的重复,可以重新优化一下,等有灵感再说)
struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
// write code here
if(head==NULL)
return head;
struct ListNode* cur1 = head;
struct ListNode* prev = head;
struct ListNode* cur2 = head;
int flag = 0; //判断cur2是否停下来了
while (cur2->next!=NULL) {
cur2=cur1;
for (int i = 1; i < k; i++) {
if (cur2->next == NULL) {
flag = 1;
break;
}
cur2 = cur2->next;
}
if (flag == 1)
break;
if (cur1 == head) {
while (head != cur2) {
head = cur1->next;
struct ListNode* tmp = cur2->next;
cur2->next = cur1;
cur1->next = tmp;
cur1 = head;
}
} else {
while (prev->next != cur2) {
prev->next = cur1->next;
struct ListNode* tmp = cur2->next;
cur2->next = cur1;
cur1->next = tmp;
cur1 = prev->next;
}
}
for (int i = 1; i < k; i++) {
if (cur2->next == NULL) {
flag = 1;
break;
}
cur2 = cur2->next;
}
prev=cur2;
cur1 = cur2->next;
}
return head;
}

京公网安备 11010502036488号