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

25. K 个一组翻转链表 - 力扣（LeetCode）

题解

递归解法

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {if (head == nullptr) return nullptr;ListNode* prev = head;ListNode* index = head->next;int m = 0;// 考虑每k个情况，单链表反转while (++m < k && index != nullptr) {prev->next = index->next;index->next = head;head = index;index = prev->next;}if (m < k) {return reverseKGroup(head, m);}// 注意这里是index，即下一组的头prev->next = reverseKGroup(index, k);return head;}
};

迭代

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* dummy = new ListNode(0, head);ListNode* prev = dummy;ListNode* cur = head;int n = 0; // 链表长度while(cur != nullptr){n ++;cur = cur->next;}n = n / k;cur = head;for(int i = 1; i <= n *(k-1); i++){ListNode* nxt = cur->next;cur->next = nxt->next;nxt->next = prev->next;prev->next = nxt;if(i % (k-1) == 0){prev = cur;cur = cur->next;}}return dummy->next;}
};