【leetcode】25-K个一组翻转链表【C++】

题目如下：

解题思路：

同样采用 递归 来解决问题。思路类似两两交换链表中节点，先对前 K 个节点翻转，然后递归调用，递归结束的条件是当前剩余节点个数小于 K 个。

代码如下：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { ListNode *cur = head; for(int i = 1; i <= k; i++){ if(cur == NULL) //当前节点不够k个，递归结束 return head; cur = cur->next; //让cur指向下一组k个节点的头部 } ListNode *new_head = reverseKNode(head, cur); //翻转当前的k个节点 head->next = reverseKGroup(cur, k); //递归调用 return new_head; } //翻转k个节点 //其中head是k个节点的头部,tail是k个节点尾部的下一个节点（即下一组k个节点的头部） ListNode* reverseKNode(ListNode *head, ListNode *tail) { ListNode *pre = tail; //存放当前翻转节点指向的next节点 while(head != tail){ ListNode *t = head->next; head ->next = pre; pre = head; head = t; } return pre; } };