- Reverse Nodes in k-Group:题目链接
跟leetcode 92. Reverse Linked List II 一样的做法 解答：戳我
方法1：穿针引线
- pre:指向带翻转节点之前的一个节点
- curNode: 当前指向的节点 简称c
- nextNode: 当前指向的下一个节点 简称n
- pCount:用来遍历从pre开始 后面的节点数是不是>=k 如果小于k退出 大于等于k翻转
基本思想：先找到带翻转节点的前驱pre所在的位置，每次将curNode放在nextNode的后面，将nextNode放在pre的后面 如下所示1
2
3
4
5
6
7
8
9
10
11
12
13k = 2
初始： dummyHead --> 1 --> 2 --> 3 --> 4 --> 5
pre c n
一次： dummyHead --> 2 --> 1 --> 3 --> 4 --> 5
pre c n
二次： dummyHead --> 3 --> 2 --> 1 --> 4 --> 5
pre c n
三次： dummyHead --> 3 --> 2 --> 1 --> 4 --> 5
pre 4到5不满足k=3 退出
AC代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26// 时间复杂度O(N) 空间复杂度O(1)
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
struct ListNode *dummyHead = (struct ListNode *) malloc(sizeof(struct ListNode));
dummyHead->next = head;
struct ListNode *pre = dummyHead, *curNode = NULL,*pCount =NULL, *nextNode = NULL;
while (1){
int i = 0;
pCount = pre; // pCount只是用来遍历从pre开始往后数满不满足K个而已
while (i< k && pCount!=NULL){
pCount = pCount->next;
i++;
}
if (NULL == pCount){ // 遍历到链表尾了
break;
}
curNode = pre->next; // 找到curNode的位置
for (i = 0; i < k - 1 && curNode != NULL; ++i) { // 开始翻转
nextNode = curNode->next;
curNode->next = nextNode->next;
nextNode->next = pre->next;
pre->next = nextNode;
}
pre = curNode; // 更新pre的位置
}
return dummyHead->next;
}
pS:源代码链接