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

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

https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024?tpId=295&tqId=663&ru=%2Fpractice%2F71cef9f8b5564579bf7ed93fbe0b2024&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj

描述

给出一个升序排序的链表,删除链表中的所有重复出现的元素,只保留原链表中只出现一次的元素。
例如:
给出的链表为1 \to 2\to 3\to 3\to 4\to 4\to51233445, 返回1\to 2\to5125.
给出的链表为1\to1 \to 1\to 2 \to 311123, 返回2\to 323.

数据范围:链表长度 0 \le n \le 100000n10000,链表中的值满足 |val| \le 1000val1000
要求:空间复杂度 O(n)O(n),时间复杂度 O(n)O(n)
进阶:空间复杂度 O(1)O(1),时间复杂度 O(n)O(n)

这个题有点意思,逻辑也不复杂。
在之前的删除重复元素的题的基础上,增加了一个难度,是要删除所有的重复元素,而不是需要留下一个。
所以需要做一个标记。
满足这个标记的时候,在删除之前节点的基础上,直接删除当前的节点。

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        ListNode *res = new ListNode(-1);
        res->next = head;
        ListNode *pre = res;
        ListNode *cur = head;
        while(cur && cur->next != NULL){
            bool flag = false;
            while(cur->next && cur->val == cur->next->val){
                flag = true;
                cur->next = cur->next->next;
            }
             
            if(flag){
                pre->next = cur->next;
            }else{
                pre = cur;
            }
            cur = cur->next;
        }
        
        return res->next;
    }
};


来吧,BAT 文章被收录于专栏

来吧,BAT

全部评论

相关推荐

04-30 21:35
已编辑
长安大学 C++
晓沐咕咕咕:评论区没被女朋友好好对待过的计小将可真多。觉得可惜可以理解,毕竟一线大厂sp。但是骂楼主糊涂的大可不必,说什么会被社会毒打更是丢人。女朋友体制内生活有保障,读研女朋友还供着,都准备订婚了人家两情相悦,二线本地以后两口子日子美滋滋,哪轮到你一个一线城市房子都买不起的996清高计小将在这说人家傻😅
点赞 评论 收藏
分享
06-03 15:32
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务