题解 | #链表中的节点每k个一组翻转#
链表中的节点每k个一组翻转
https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* reverseKGroup(ListNode* head, int k) {
// write code here
auto dummy = new ListNode(-1), p = dummy;
dummy->next = head;
while (true) {
auto q = p;
for (int i = 0; i < k && q; i++) q = q->next;
if (!q) break;
auto a = p->next, b = a->next;
for (int i = 0; i < k - 1; i++) {
auto temp = b->next;
b->next = a;
a = b;
b = temp;
}
auto c = p->next;
c->next = b;
p->next = a;
p = c;
}
return dummy->next;
}
};
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* reverseKGroup(ListNode* head, int k) {
// write code here
auto dummy = new ListNode(-1);
dummy->next = head;
auto pre = dummy;
while (true) {
auto p = pre;
for (int i = 0; i < k; i++) {
if (!p->next) return dummy->next;
p = p->next;
}
auto cur = pre->next;
for (int i = 0; i < k - 1; i++) {
auto temp = cur->next;
cur->next = temp->next;
temp->next = pre->next;
pre->next = temp;
}
pre = cur;
}
return dummy->next;
}
};
- 思路：分组反转
- 1、设置空节点
- 2、pre指针指向反转组的前一个节点
- 3、首先判断反转组内节点数是否达到k个，不满足k个则直接返回
- 4、反转组内节点，然后将调整指针
- 时间复杂度：O(n)
- 空间复杂度：O(1)
