题目讲解

25. K 个一组翻转链表

算法讲解

虽然这道题是一道困难题，但是从代码层面很简单，只是一道简单的模拟：我们要先求出总共需要翻转的链表有多少组（链表的长度 / k），接下来就是翻转k的链表最链接的问题

翻转n个链表我们使用头插法，注意：当第一组链表翻转完成之后，我们就不能在使用上一次的头插法的头结点了，就需要在新的链表的尾结点使用头插法，所以我们每一次在翻转当前组链表的时候需要记录翻转完成之后的尾结点，这个尾结点特别好找，就是当前链表组的首节点，使用prev变量记录下来就行

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int ListNodeLength(ListNode* head)
    {
        if(head == nullptr)return 0;
        return 1 + ListNodeLength(head->next);
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        //需要翻转几个链表组
        int n = ListNodeLength(head) / k;

        //使用头插法 翻转链表
        ListNode* newhead = new ListNode(-1);
        ListNode*phead = newhead;

        //prev记录翻转之后最后一个节点
        ListNode* prev = nullptr;
        ListNode* cur = head;
        ListNode* Next = cur->next;
        for(int i = 0; i < n; i++)
        {
            //这个for是遍历需要翻转的链表组
            prev = cur;  //记录翻转之后的尾结点
            int cnt = k;
            while(cnt--)
            {
                cur->next = phead->next;
                phead->next = cur;
                cur = Next;
                if(Next)Next = Next->next;
            }
            //走到这里一个链表组的翻转链接工作已经完成  需要从新的链表的尾节点开始链接下一组翻转链表
            phead = prev;
        }
        //走到这里说明翻转的链表组全部链接完成  之后链接剩余的链表
        phead->next = cur;
        phead = newhead->next;
        delete newhead;
        return phead;
    }
};