LeetCode每日一题——K个一组翻转链表

题目描述：给定链表的头节点head，每k个节点一组进行翻转，返回操作后的链表。

示例：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

我们可以先处理翻转整个链表的情况

ListNode* reverseList(ListNode* head) { ListNode* cur = head; ListNode* pre = nullptr; while (cur) { ListNode* tmp = cur->next; cur->next = pre; pre = cur; cur = tmp; } return pre; }

又因为k个一组，所以可以优化到翻转某一段区间上的链表

ListNode* reverseList(ListNode* m,ListNode* n){ ListNode* cur=m; ListNode* pre=nullptr; while(cur!=n){ ListNode* tmp=cur->next; cur->next=pre; pre=cur; cur=tmp; } return pre; }

最后递归，注意讨论k=1的情况

ListNode* reverseList(ListNode* m,ListNode* n){ ListNode* cur=m; ListNode* pre=nullptr; while(cur!=n){ ListNode* tmp=cur->next; cur->next=pre; pre=cur; cur=tmp; } return pre; } ListNode* reverseKGroup(ListNode* head, int k) { if(k==1){ return head; } ListNode* p=head; ListNode* q=head; for(int i=0;i<k;++i){ if(p==nullptr){ return head; } p=p->next; } ListNode* newHead=reverseList(q,p); q->next=reverseKGroup(p,k); return newHead; }