方法一 模拟法
将一条链表分块分为链表长度/k块链表，如果处不尽则说明后面会有剩下的那一块是不满长度为k的。在最初的时候需要定义两个NodeList表示res(结果)和 now(当前所到达的结果链表的位置)。之后遍历块的长度，对每一个链表块进行翻转，再翻转完后将完成的链表插入到now链表的下一个，再将now链表更新到最前即可。
/**
* 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
if(k <= 1)return head;
if(head == nullptr)return head;
ListNode* node = head;
int len = lenListnode(head);
head = node;
int n = len / k;//翻转的组数
ListNode* res = new ListNode(0);
ListNode* cur = res;
for(int i = 0; i < n; i++){//按组反转
ListNode* temp = nullptr;
for(int j = 0; j < k; j++){//反转链表
ListNode* t = head->next;
head->next = temp;
temp = head;
head = t;
}
cur->next = temp;
while(cur->next != nullptr)cur = cur->next; 将cur更新到最前的一个点
}
cur->next = head;//接上凑不齐k个的多余元素
return res->next;
}
//获得链表长度
int lenListnode(ListNode* head){
int len = 0;
while(head != nullptr){
head = head->next;
len++;
}
return len;
}
};
方法二 栈
和方法一一样将链表分成每段长度为k的子链表，将每个链表存入栈中，当栈中有k个元素即可一一取出，之后按取出的顺序重组链表就是这一段中翻转的链表，要注意的是处理尾部不满长度为k的链表块时直接取栈底的元素做为最后一段即可。
/**
* 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
if(k <= 1)return head;
if(head == nullptr)return head;
stack<ListNode*>stk;
ListNode* res = new ListNode(0);
ListNode* now = res;
int cnt = 0;
while(true){
for(int i = 0; i < k; i++){//将当前链表前k个存入栈中
stk.push(head);
head = head->next;
cnt++;
if(head == nullptr)break;
}
if(cnt == k){//如果当前栈中有k个元素则一一取出存入链表
while(!stk.empty()){
now->next = stk.top();
stk.pop();
now = now->next;
now->next = nullptr;
}
}
if(head == nullptr)break;//如果链表取完了跳出循环
cnt = 0;
}
ListNode* end = nullptr;
while(!stk.empty()){//如果栈中还有剩下的就说明是最后的一块直接取栈底即可
end = stk.top();
stk.pop();
}
now->next = end;
return res->next;
}
};
