【牛客刷题-算法】NC25 删除有序链表中重复的元素-I

简介: 【牛客刷题-算法】NC25 删除有序链表中重复的元素-I

1.题目描述


描述

删除给出链表中的重复元素(链表中元素从小到大有序),使链表中的所有元素都只出现一次

例如:

给出的链表为1 → 1 → 2 1\to1\to21→1→2,返回1 → 2 1 \to 21→2.

给出的链表为1 → 1 → 2 → 3 → 3 1\to1\to 2 \to 3 \to 31→1→2→3→3,返回1 → 2 → 3 1\to 2 \to 31→2→3.


数据范围:链表长度满足 0 ≤ n ≤ 100 0≤n≤1000≤n≤100,链表中任意节点的值满足 ∣ v a l ∣ ≤ 100 ∣val∣≤100∣val∣≤100

进阶:空间复杂度 O(1)O(1),时间复杂度 O(n)O(n)


image.png


2.算法设计思路


总体思路:遍历一次链表,过程中删除重复的元素。

算法过程:


从头结点开始遍历,终止条件为当前结点的下一个结点为空。

对遍历到的结点,与后一个结点的值比较;若值相同,则删除后面那个结点。直到当前结点与后一个结点的值不同时,才继续遍历下一个结点。

结点的删除方式:将当前结点的下一个结点修改为当前结点后面第二个结点,并释放删除结点的内存。

复杂度:


时间复杂度:o ( n ) o(n)o(n)

空间复杂度:o ( 1 ) o(1)o(1)(指除链表本身外,额外用到的空间)


3.算法实现


注:这里并不是完整代码,而只是核心代码的模式


/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        ListNode* p = head;
        while(p != nullptr && p->next != nullptr){
            if(p->val == p->next->val){
                ListNode* t = p->next;
                p->next = p->next->next;
                delete t;
            }
            else
                p = p->next;
        }
        return head;
    }
};

4.运行结果


成功通过!


相关文章
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
210 3
|
6月前
|
存储 算法 物联网
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
125 0
|
7月前
|
存储 监控 算法
员工电脑监控系统中的 C# 链表算法剖析-如何监控员工的电脑
当代企业管理体系中,员工电脑监控已成为一个具有重要研究价值与实践意义的关键议题。随着数字化办公模式的广泛普及,企业亟需确保员工对公司资源的合理利用,维护网络安全环境,并提升整体工作效率。有效的电脑监控手段对于企业实现这些目标具有不可忽视的作用,而这一过程离不开精妙的数据结构与算法作为技术支撑。本文旨在深入探究链表(Linked List)这一经典数据结构在员工电脑监控场景中的具体应用,并通过 C# 编程语言给出详尽的代码实现与解析。
127 5
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
239 30
|
8月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
384 25
|
8月前
|
存储 监控 算法
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
140 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
|
11月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
11月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
16天前
|
数据采集 分布式计算 并行计算
mRMR算法实现特征选择-MATLAB
mRMR算法实现特征选择-MATLAB
76 2
|
29天前
|
传感器 机器学习/深度学习 编解码
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
147 3

热门文章

最新文章