题解 | #删除有序链表中重复的元素-II#

删除有序链表中重复的元素-II

https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024

摸了两天的🐟qaq,终于回来了,不过脑子有点生了>w<

言归正传,这道题相比于上一道题增加的功能是要求将重复的元素全部删除,而且要求的空间复杂度为O(1),这就意味着我们需要在原本的链表上操作了。

因为考虑到头节点就有可能是重复的节点,所以我们准备在原本的head的前面添加一个pre_head作为新的头节点,这个节点在后续程序中会认为是已完成重复性判断的节点~

因为我们需要在原本的链表上进行删除操作,因此还需要一个aft_head在原本的head的后面,当然aft_head还需要担任重复性判断的任务

最后我们需要一个detect_repeat用于重复性判断~

讲完了我们会用到的新变量,我们该来准备算法流程啦~

主要的流程是,判断head当前的节点是否为重复的节点,如果是重复的,则需要一直进行判断+删除操作,直到删除完所有的重复节点,如果不是重复节点则进行常规的->next操作

现在我们来说一下边界状态,简单的单个节点链表以及空链表就不说了

首先是头节点就是重复元素的情况,由于pre_head的使用头节点重复不会导致影响

然后就是尾节点是重复元素,这就意味着aft_head会是NULL的情况

        if(detect_repeat==aft_head->val)//有重复的,需要删除重复的第一个元素
        {
            while(head->val==detect_repeat)
            {
                pre_head->next = aft_head;
                if(head==output)
                {
                    output = output->next;
                }
                free(head);
                head = pre_head->next;
                if(head==NULL)
                {
                    break;
                }
                if(aft_head!=NULL)
                {
                    aft_head = aft_head->next;
                }
            }
        }

所以我们需要添加aft_head!=NULL的条件以及在head==NULL的情况下break的条件

最后添加一下完整的函数代码,这道题我也通过的莫名其妙的QAQ,大佬们看到问题请劳烦评论区告知我感谢感谢~

struct ListNode* deleteDuplicates(struct ListNode* head ) {
    struct ListNode* pre_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(pre_head!=NULL)
    {
        pre_head->next = head;
        pre_head->val = -1001;
    }
    if(pre_head->next==NULL)
    {
        return NULL;
    }
    int detect_repeat = -1001;
    struct ListNode* aft_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(aft_head!=NULL)
    {
        aft_head = head->next;
    }
    if(aft_head==NULL)
    {
        return head;
    }
    struct ListNode* output = head;
    while(aft_head!=NULL)
    {
        detect_repeat = head->val;
        if(detect_repeat==aft_head->val)//有重复的,需要删除重复的第一个元素
        {
            while(head->val==detect_repeat)
            {
                pre_head->next = aft_head;
                if(head==output)
                {
                    output = output->next;
                }
                free(head);
                head = pre_head->next;
                if(head==NULL)
                {
                    break;
                }
                if(aft_head!=NULL)
                {
                    aft_head = aft_head->next;
                }
            }
        }
        else 
        {
            pre_head = pre_head->next;
            head = head->next;
            aft_head = aft_head->next;
        }
    }
    return output;
}

全部评论

相关推荐

会飞的猿:我看你想进大厂,我给你总结一下学习路线吧,java语言方面常规八股要熟,那些java的集合,重点背hashmap八股吧,jvm类加载机制,运行时分区,垃圾回收算法,垃圾回收器CMS、G1这些,各种乐观锁悲观锁,线程安全,threadlocal这些。在进阶一些的比如jvm参数,内存溢出泄漏排查,jvm调优。我这里说的只是冰山一角,详细八股可以去网上找,这不用去买,都免费资源。mysql、redis可以去看小林coding,我看你简历上写了,你一定要熟,什么底层b+树、索引结构、innodb、mvcc、undo log、redo log、行级锁表级锁,这些东西高频出现,如果面试官问我这些我都能笑出来。消息队列rabbitmq也好kafka也好,学一种就行,什么分区啊副本啊确认机制啊怎么保证不重复消费、怎么保证消息不丢失这些基本的一定要会,进阶一点的比如LEO、高水位线、kafka和rocketmq底层零拷贝的区别等等。计算机网络和操作系统既然你是科班应该理解起来问题不大,去看小林coding这两块吧,深度够了。spring boot的八股好好看看吧,一般字节腾讯不这么问,其他的java大厂挺爱问的,什么循环依赖啥的去网上看看。数据结构的话科班应该问题不大,多去力扣集中突击刷题吧。项目的话其实说白了还是结合八股来,想一想你写的这些技术会给你挖什么坑。除此之外,还有场景题、rpc、设计模式、linux命令、ddd等。不会的就别往简历上写了,虽然技术栈很多的话好看些,但背起来确实累。总结一下,多去实习吧,多跳槽,直到跳到一个不错的中厂做跳板,这是一条可行的进大厂的路线。另外,只想找个小厂的工作的话,没必要全都照这些准备,太累了,重点放在框架的使用和一些基础八股吧。大致路线就这样,没啥太多难度,就是量大,你能达到什么高度取决于你对自己多狠,祝好。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务