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

2022 年 10 月 04 日
湖南
本文字数：773 字
阅读完需：约 3 分钟

个人主页：CSDN清风莫追
推荐一款面试、刷题神器牛客网：👉点击加入刷题大军👈

1.题目描述

描述删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次例如：给出的链表为 $1 \to 1 \to 2$ ,返回 $1 \to 2$ .给出的链表为 $1 \to 1 \to 2 \to 3 \to 3$ ,返回 $1 \to 2 \to 3$ .

数据范围：链表长度满足 $0 \leq n \leq 100$ ，链表中任意节点的值满足 $∣ v a l ∣ \leq 100$ 进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

2.算法设计思路

总体思路：遍历一次链表，过程中删除重复的元素。算法过程：

从头结点开始遍历，终止条件为当前结点的下一个结点为空。
对遍历到的结点，与后一个结点的值比较；若值相同，则删除后面那个结点。直到当前结点与后一个结点的值不同时，才继续遍历下一个结点。
结点的删除方式：将当前结点的下一个结点修改为当前结点后面第二个结点，并释放删除结点的内存。

复杂度：

时间复杂度： $o (n)$
空间复杂度： $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.运行结果

成功通过！

结束语：

今天的分享就到这里啦，快来加入刷题大军叭！👉点击开始刷题学习👈

感谢阅读

个人主页：CSDN清风莫追

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/8cb11ae6d05b3a766c60ed8c7】。文章转载请联系作者。

清风莫追

关注

还未添加个人签名 2022.08.09 加入

编程一学生

发布

暂无评论

创作场景