class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
auto dummy=new ListNode(-1);
dummy->next=head;//虚拟头节点
for (auto p=dummy;;){
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++){//翻转k-1个next指针
auto c=b->next;
b->next=a;
a=b,b=c;
}
//出来时 a是第n*k给节点 b是第n*k+1个节点
//a的next指针指向上一个节点 b指向下一个节点
// 1->2->3->4->5->6->7
// 1<-2<-3 4->5->6->7
// p->1...<-a b->5->6->7
// p->c...<-a b->5->6->7
// p->a...->c->b->5->6->7
// ....
// p->3->2->1->6->5->4->7
auto c=p->next;
p->next=a,c->next=b;
p=c;
//处理区间首尾 原来的区间第一个要指向区间最后一个所指向的
//原来指向区间第一个的要指向区间最后一个
//具体看上方字符演示
}
return dummy->next;
}
};
0x3f 解法
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
auto dummy=new ListNode(-1);
dummy->next=head;//虚拟头节点
ListNode *p0=dummy->next;
int n=0;
while (p0) {
p0=p0->next;
n++;
}
p0=dummy;
ListNode* pre=NULL;
ListNode* cur=p0->next;
while (n>0){
for (int i=0;i<min(n,k);i++){
ListNode *t=cur->next;
cur->next=pre;
pre=cur;
cur=t;
}
n-=k;
ListNode* ne;
ne=p0->next;
p0->next->next=cur;
p0->next=pre;
p0=ne;
//如果要求剩下的也翻转 改成下面
// if (n>0) ne=p0->next;
// p0->next->next=cur;
// p0->next=pre;
// if (n>0) p0=ne;
}
return dummy->next;
}
};
解法二:递归
参考自
class Solution {
public:
ListNode* reverse(ListNode* head, ListNode* tail) //反转链表模板,面试高频题
{
ListNode *pre = head, *cur = head->next;
while (cur != tail)
{
ListNode* ne = cur->next;
cur->next = pre;
pre = cur, cur = ne;
}
head->next = nullptr;
return pre;
}
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == nullptr || head->next == nullptr) return head;
ListNode* tail = head;
for (int i = 0; i < k; ++ i){ //遍历k个节点
if (tail == nullptr) return head; //不足k个节点则不反转,直接返回
//注意,如果这里面试官要求最后不足k个也要翻转,就得改成下面一行
//if (tail == nullptr) return reverse(head, tail);
tail = tail->next;
}
ListNode* newhead = reverse(head, tail); //反转长度为k的链表
head->next = reverseKGroup(tail, k); //递归将下一段反转链表接到当前段的尾部
return newhead;
}
};