首页 > 试题广场 >

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

[编程题]删除有序链表中重复的元素-II

热度指数：193212 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围：链表长度 $0 \le n \le 10000$ ，链表中的值满足 $|val| \le 1000$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,2}

输出

{1}

示例2

输入

{}

输出

{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

牛客题解官

发表于 2022-04-22 11:37:29

精华题解题目的主要信息：在一个非降序的链表中，存在重复的节点，删除该链表中重复的节点重复的节点一个元素也不保留举一反三：学习完本题的思路你可以解决如下题目： BM15.删除有序链表中重复的元素-I 方法一：直接比较删除（推荐使用）思路：这是一个升序链表，重复的节点都连在一起，我们就可以很轻易展开全文

牛一霸

发表于 2021-07-09 21:05:10

精华题解题目：删除有序链表中重复的元素描述：给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。例如：给出的链表为1→2→3→3→4→4→5，返回1→2→5。给出的链表为1→1→1→2→3，返回2→3。示例1：输入：{1,2,2}，返回值：{1} 展开全文

冰箱的主人LR

发表于 2021-07-06 23:11:07

精华题解牛客NC24#删除有序链表中重复的元素-II# 题目链接描述给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。例如：给出的链表为1→2→3→3→4→4→5, 返回1→2→5.给出的链表为1→1→1→2→3, 返回2→3. 题目很简单，因为给的是升序链表相同的展开全文

鸠摩罗什

发表于 2021-07-11 13:53:49

精华题解描述给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。例如：给出的链表为1→2→3→3→4→4→5, 返回1→2→5.给出的链表为1→1→1→2→3, 返回2→3.示展开全文

大菠萝侦探

发表于 2021-07-10 00:49:50

精华题解描述给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。首先提出这个题比较不严谨的地方，代码中一开始给出的注释中，结构体的定义是不严谨的，虽然注释中定义的结构体是下面的样子 /** * struct ListNode { * int val; * 展开全文

蒙牛麦片

发表于 2021-07-16 17:29:47

精华题解 NC24 删除有序链表中重复的元素-II 题意分析：给一个有序的链表，删除其中出现的重复元素示例：链表1→2→3→3→4→4→5, 删除重复元素后，变为1→2→5。解释：在原有链表中，3和4出现了多次，因此把所有的3,4都删除，最后返回了1→2→5。题解一（遍历）：在NC25中，我们删除了重展开全文

下一次什么时候可以修改昵称

发表于 2020-10-20 10:20:00

算法 1.设置伪结点，方便处理 2.双指针prev和curr 3.当遇到当前节点值和下一节点值相等的节点时，进行while循环找到下一个不相等的节点，挂到prev节点上 4.当遇到当前节点值和下一节点值不相等的节点时，prev和curr都移动到下一个节点接着遍历就行 public ListNo 展开全文

OfferCall！

发表于 2021-03-27 20:45:54

先定义一个头节点用于指示链表的头部位置，方便最后返回链表。然后定义两个指针p和q，初始化时，p先指向头结点，q指向head，开始遍历链表，因为链表是有序的，所以重复元素一定是连续出现的，所以我的策略就是先找出重复的一段子链表，然后一网打尽，具体做法就是：如果q.next.val != q.v 展开全文