LeetCode Hard｜【25. K 个一组翻转链表】

力扣题目链接

首先我们考虑一种很直观的思路：

• 遍历链表，统计链表长度
• 遍历链表，进行翻转
  • 对于每一组长度为 K 的节点，进行翻转
  • 如果剩余节点不足 K 个，则不进行翻转
• 连接翻转后的子链表
  这里我们用的就是只用 O(1) 额外内存空间的算法

关于如何 k 个节点个数的链表

我认为这里最重要的是链表的翻转，当你知道需要翻转的链表长度的时候，这个方法应该按照固定模版来进行，也就是我们的三指针：

for (int i = 1; i < k; i++) {
	cur->next = nex->next;
	nex->next = pre->next;
	pre->next = nex;
	nex = cur->next;
}
1
2
3
4
5
6

但是还记得我们之前在做反转链表题目的时候是怎么处理的嘛：

while (cur) {
	ListNode *nex = cur->next;
	cur->next = pre;
	pre = cur;
	cur = nex;
}
1
2
3
4
5
6

这里简单直观多了，最大的区别是什么呢？

首先，做整表翻转的时候，我们的逻辑非常简单
其次，对于对 k 个节点分组翻转，并且我们还必须做到对剩余的 k 个节点不进行翻转，势必有这样形式的代码：

while (cout >= k) {
	...
	for (...) {
		...
	}
	...
	count -= k;
}
1
2
3
4
5
6
7
8

CPP总体代码：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || k == 1) return head;

        ListNode *dummyHead = new ListNode();
        dummyHead->next = head;
        ListNode *cur = dummyHead, *pre = dummyHead, *nex = dummyHead;
        int count = 0;

        cur = head;

        while (cur) {
            cur = cur->next;
            count++;
        }

        while (count >= k) {
            cur = pre->next;
            nex = cur->next;
            for (int i = 1; i < k; i++) {
                cur->next = nex->next;
                nex->next = pre->next;
                pre->next = nex;
                nex = cur->next;
            }
            pre = cur;
            count -= k;
        }

        return dummyHead->next;
        
    }
};
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
27
28
29
30
31
32
33
34