leetcode 25. K 个一组翻转链表

骑猪看日落 2023-07-02 03:19 30阅读 0赞

(反转链表最难一题)

会这题，leetcode其他的链表题应该都不是问题了。

这题总的来说也很好写，一开始没有注意用双指针，走了很多弯路，后面尝试用双指针后很快就写好了。

这题要详细的写一下分析过程。

首先，我的思路还是dfs。在回溯的时候进行修改。怎么做呢？

首先，dfs的时候计数，比如链表1->2->3->4->5  k=3

我用n来记录当前是第几个数。

当dfs到5时，n=5,并且这已经是最后一个数了，这时，如果n%k==0，代表这组数可以被k均分，也就是从这个数开始，往前找k个数，就是一组了。如果n%k!=0 ，说明最后的这个数不用分组。

还是用有5个数的链表来分析，

n==5 ,n%3==2,不用管它

n==4, n%3==1,不用管它

n==3 n%3==0 从它开始便是一个分组了，那么让当前节点指向前一个节点即可。

现在还有一个问题，1不用指向前一个节点，因为它是一组的结尾。如何判断呢？ 其实当n%k==1时，我们就可以判断它是一个组的结尾。当然你可能发现4%3也等于1 ，所以我加了一个标志位f，来判断分组到底开不开始。n=5,n=4时，分组未开始，所以不用管，当n=1时，分组已经开始了。所以需要让它指向前一个分组的开始，或者是最后一个未分组节点（例如4）

用second指向前一个分组的开始节点，用first指向当前分组的开始节点。每遇到n%k==0，让second=first, first=当前节点即可。

文字的力量还是有限的。看代码可能更直观一点。

/**
     * 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) {
            if(head==NULL||k==1) return head;  //特例
            ListNode *first = NULL;
            ListNode *second = NULL;
            bool f=0;
            dfs(head,NULL,first,second, 1,k,f);
            return first;
        }
       void dfs(ListNode *head,ListNode *pre,ListNode *&first, ListNode *&second, int n,int k,bool &f)
        {
            if(head->next==NULL)  //最后一个节点
            {
                if(n%k==0)  //最后一个节点可以分组
                {
                    f=1;//标记分组开始
                    if(pre==NULL){} //处理只有一个节点的情况
                    else{
                        head->next=pre;//开始反转
                        second=first;
                        first=head;//记录当前组的开始
                    }
                }
                else{ //不能分组，也要记录
                    second=first;
                    first=head;
                }
            }
            else
            {
                dfs(head->next,head,first,second, n+1,k,f);// 搜索
               // 下面是回溯过程
                if(f||n%k==0) //f==1代表分组已经开始，n%k==0代表分组可以开始
                {
                    if(n%k==0){ //一个分组的开始
                        head->next=pre;
                        if(f==0)
                        {
                            f=1;//若是第一分组，则标记一下
                        }
                        second=first;
                        first=head;
                    }
                    else if(n%k==1){ //分组的结尾，指向前一个分组的头，或最后一个未分组节点
                            head->next=second;
                    } 
                    else{
                       head->next=pre;
                    }
                }
                else //还未开始分组
                {
                    second=first;
                    first=head;
                }
            }
        }
    };