题解 | #链表中的节点每k个一组翻转#
链表中的节点每k个一组翻转
https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
与反转题目基本相同，这里的难点就是找范围，在范围里进行交换。
准备工作：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;
}
Momenta公司福利 341人发布