题解 | #链表中的节点每k个一组翻转#
链表中的节点每k个一组翻转
http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
将任务分成每K个节点处理，如果没有K个节点，直接返回head，否则利用一个函数翻转这K个节点，并且在翻转时候记录下来后驱节点（下一次递归时候使用）。然后对链表的后驱节点继续进行递归，直到处理结束。
class Solution {
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* backNext=nullptr;
ListNode* reverseK(ListNode* head, int k){
if (k == 1) {
backNext = head->next;
return head;
}
ListNode* last = reverseK(head->next, k - 1);
head->next->next = head;
head->next = backNext;
return last;
}
ListNode* reverseKGroup(ListNode* head, int k) {
// write code here
if(!head||k<=1)
return head;
ListNode* cur=head;
for(int i=0;i<k;++i){
if(!cur)
return head;
cur=cur->next;
}
auto last=reverseK(head,k);
head->next=reverseKGroup(backNext,k);
return last;
}
};
上海智元新创技术有限公司公司福利 5人发布