LeetCode 25 Reverse Nodes in k-Group
题目分析
https://leetcode.com/problems/reverse-nodes-in-k-group/
迭代法
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
if (head == nullptr) return head;
if (k == 1) return head;
int n = 0;
ListNode *next = head;
while (next != nullptr) {
n++;
next = next->next;
}
int stop = k * int(n / k);
int count = -1;
ListNode dummyNode;
ListNode *prevGroupHead = &dummyNode;
ListNode *groupHead = head;
ListNode *c = head;
ListNode *cn = c->next;
while (true) {
count++;
// c is the count-th node, start from 0
if (count == stop) break;
if ((count + 1) % k == 0) {
// cn is in next group
prevGroupHead->next = c;
// The old head becomes the tail
prevGroupHead = groupHead;
groupHead = cn;
// Update c & cn
if (cn) {
c = cn;
cn = cn->next;
} else {
break;
}
} else {
auto cnn = cn->next;
cn->next = c;
c = cn;
cn = cnn;
}
}
prevGroupHead->next = groupHead;
return dummyNode.next;
}
};
递归法
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* c = head;
int count = 1;
while (c) { // 循环结束要么 c 为 nullptr
if (count == k) {
break; // 要么够了，此时 c 必不为 nullptr
}
count++;
c = c->next;
}
if (!c) return head; // 所以只需要判断 c 是否是 nullptr 就好
auto rest = reverseKGroup(c->next, k);
c->next = nullptr;
auto temp = reverse(head);
head->next = rest;
return temp;
}
ListNode* reverse(ListNode* head) {
if (!head || !head->next) return head;
auto temp = reverse(head->next);
head->next->next = head;
head->next = nullptr;
return temp;
}
};