-
相似题目:lc 92. 反转链表 II
题目
思路
代码
// pre 指向 需要翻转的 局部链表的 第1个结点 的 之前的结点
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
auto dummy = new ListNode(-1), pre = dummy;
dummy->next = head;
// 改成 while(1)也可, 因为跳出循环是靠下面的 break.
// while(head)可以特判 head == null 情况, 不用等到下面break 就提前跳出
// while(pre->next) 可以特判 head == null 和 pre->next == null 的情况
while (pre->next) {
// 1. 判断是否 还有 k 个结点
auto q = pre->next;
for (int i = 1; i < k && q; i ++ ) q = q->next; // 能否移动 k - 1 次
if (!q) break; // 跳出 for循环, 要么 1.移动了k-1次,q不为空; 2.q为空,不够k个
// 1. 判断是否 还有 k 个结点
// int cnt = 0;
// for (auto q = pre->next; q && cnt <= k; q = q->next) cnt ++ ;
// if (cnt < k ) break;
// 2.1 局部翻转链表
auto a = pre->next, b = a->next;
for (int i = 1; i < k; i ++ ) { // k-1 次. 注意 不能while(--k), k值 不能变动
auto c = b->next;
b->next = a;
a = b, b = c;
}
// 2.2 处理 局部链表 首尾结点 处的 连接情况
head = pre->next; // 用 head 暂存 pre->next
pre->next = a, head->next = b;
// 2.3 pre 更新为 下一段需要局部翻转的链表段的 前一个结点, 即 b之前的结点 head
pre = head; // pre需要指向b之前的结点, b之前的结点是 head 而不是 a !!!
}
return dummy->next;
}
};
感谢分享