欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode-25:K 个一组翻转链表

程序员文章站 2022-07-08 13:24:07
...

一、题目描述

LeetCode-25:K 个一组翻转链表

二、解题思路

  这道题,最简单的方法就是从头节点开始,每次查看当前剩下的节点是不是多于K个,如果是的话就进行反转,否则就不进行并返回。
  这样当然可以,但是有性能瓶颈:每次都需要查看剩余元素个数,相当于遍历了两次链表才可以完成反转,还不考虑反转的操作占用时间。
  我想出来的办法是每次都进行反转,不考虑最后的不足K个的那段不需要反转的问题。那么就势必要解决最后这一点零头的问题。
  通过前后指针,记录下当前被反转段的头节点和尾节点,反正都是要用循环的,顺手就可以判断是不是少于K个。如果少于K个,就通过记录下来的前后指针将最后的零头反转即可,而不用每次都先判断长度,然后再反转,提高了一些速度。

三、解题代码

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummyHead = new ListNode(-1);
        dummyHead->next = head;
        ListNode* newHead = new ListNode(-1);
        auto l = newHead;
        ListNode* r = nullptr;
        auto p = newHead;
        auto before = newHead;
        bool ShouldClean = false;
        while(dummyHead->next){
            int i;
            if(p != newHead)    before = r;
            for(i = 0; i < k && dummyHead->next; i++){
                auto ins = dummyHead->next;
                if(!i)    r = ins;
                dummyHead->next = ins->next;
                ins->next = p->next;
                p->next = ins;
            }
            l = p->next;
            p = r;
            if(i < k)   ShouldClean = true;
        }
        delete dummyHead;
        dummyHead = nullptr;
        
        if(ShouldClean){
            auto cleanNode = new ListNode(-1);
            while(before->next){
                auto del = before->next;
                before->next = del->next;
                del->next = cleanNode->next;
                cleanNode->next = del;
            }
            before->next = cleanNode->next;
            delete cleanNode;
            cleanNode = nullptr;
        }
        auto ret = newHead->next;
        delete newHead;
        newHead = nullptr;
        return ret;
    }
};

四、运行结果

LeetCode-25:K 个一组翻转链表

相关标签: LeetCode 链表