题解 | #链表中的节点每k个一组翻转#

核心思想

• 递归的方式
• 每次判断待翻转链表是否小于K
• 每k个结点翻转也用递归的方式

/**
 * struct ListNode {
 *	i/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode * reverse(struct ListNode * head, struct ListNode * tail)
{
    if(head->next == tail)
    {
       return head;
    }
    
    struct ListNode * newTail = NULL;
    newTail = reverse(head->next, tail);
    head->next->next = head;
    head->next = NULL;
    
    return newTail;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    // 空链表
    if(head == NULL || k == 1)
    {
        return head;
    }
    
    // 从头开始，没k个结点翻转一次，直到没有结点或不足k个元素返回
    struct ListNode * curl = head;
    // i从0起步，curl从head开始，等跳出该循环时候，curl指的应该是第k+1个结点
    // 当然不足k个结点时候，就返回head了
    for(int i = 0; i < k; i++)
    {
        if(curl == NULL)
        {
            return head;
        }
        
        curl = curl->next;
    }
    
    // 每k个元素翻转，编写独立翻转函数。 
    struct ListNode * newTail = NULL;
    newTail = reverse(head, curl);
    
    head->next = reverseKGroup(curl , k);
    
    
    // 最终返回head
    return newTail;
}