Java 数据结构之删除链表中重复的结点
作者:2021dragon 发布时间:2023-11-28 15:36:22
标签:Java,删除,链表,结点
核心考点:链表操作,临界条件检查,特殊情况处理
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。
解析一:(不提倡)
解决该问题较简单,且在写代码时不易出错的做法如下:
遍历一遍链表,记录重复结点的结点值。
再遍历一遍链表,逐个删除重复结点。
动图演示:
该方法需要遍历两遍链表,且需要开辟额外的内存空间存储重复结点的结点值,所以一般不提倡。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
if(pHead == nullptr||pHead->next == nullptr) //链表为空或只有一个结点无需进行操作
return pHead;
ListNode* cur = pHead;
unordered_set<int> filter;
//1、遍历链表找出重复的结点,将结点值存入filter
while (cur->next)
{
if (cur->val == cur->next->val)
filter.insert(cur->val);
cur = cur->next;
}
//2、逐个删除重复的结点
//先删除头部的重复结点
while(pHead&&filter.find(pHead->val) != filter.end())
{
pHead = pHead->next;
}
if(pHead == nullptr)
return nullptr;
//再删除其余的重复结点
ListNode* prev = pHead;
ListNode* last = prev->next;
while(last)
{
if(filter.find(last->val) != filter.end())
{
prev->next = last->next;
last = last->next;
}
else
{
prev = prev->next;
last = last->next;
}
}
return pHead; //返回链表头指针
}
};
解析二:(正解)
我们当然应该尽可能在遍历一遍链表的情况下解决该问题,这时我们需要使用两个指针配合完成,该过程当中包含大量细节,大致步骤如下:
1.为了后续操作方便,先为该链表创建一个头结点。
2.使用指针prev和last遍历链表,初始时prev指向头结点,last指向头结点的下一个结点。
3.当last指向的结点值与其后一个结点的结点值相同时,last独自后移,直到last指向结点的结点值与其下一个结点的结点值不同为止,此时让prev指向的结点指向last的后一个结点,最后让last指向下一个结点(图中未后移)。
4.当last指向的结点值与其后一个结点的结点值不同时,prev和last一同向后移。
如此进行下去,直到last将链表遍历完,链表当中重复的结点也就全部被删除了,最后返回头结点指向的链表即可。
动图演示:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
if (pHead == nullptr || pHead->next == nullptr) //链表为空或只有一个结点无需进行操作
return pHead;
ListNode* head = new ListNode(0); //创建头结点(便于操作)
head->next = pHead; //头结点与原链表建立关系
ListNode* prev = head;
ListNode* last = prev->next;
while (last)
{
//未发现重复的结点,prev和last一同后移
while (last->next&&last->val != last->next->val)
{
prev = prev->next;
last = last->next;
}
//发现重复的结点,last独自后移
while (last->next&&last->val == last->next->val)
{
last = last->next;
}
//到达此处有三种情况:
//1、没有需要删除的重复结点,是因为last->next == nullptr到此
//2、有需要删除的重复结点,是因为last->next == nullptr到此(链表后半段都需要删除)
//3、有需要删除的重复结点,是因为last->val != last->next->val到此(链表中间某段需要删除)
if (prev->next != last) //说明有需要删除的重复结点
{
prev->next = last->next;
}
last = last->next;
}
return head->next; //返回链表头指针
}
};
来源:https://blog.csdn.net/chenlong_cxy/article/details/120649781
0
投稿
猜你喜欢
- 为什么Android要申请权限简单说下在Android6.0及6.0以上一些google认为涉及“危险和用户隐私”的一些权限不仅要做清单文件
- import java.io.BufferedInputStream;import java.io.BufferedOutputStream
- 对接前端后效果展示如图:1、CPU相关信息实体类/** * CPU相关信息 * * @author csp */public class
- 其他的不多说了!我们来看看效果吧 一、实现方式一:直接引入compile方式A
- 今天重新装了编译器,结果崩无极限,真是日了狗了了。刚刚才知道问题在哪边。好了,说正事,对于ios开发我没接触,不是很了解,百度了半天,差不多
- 本文实例汇总了Java的System.getProperty()方法获取信息的用法。分享给大家供大家参考。具体如下:System.out.p
- 引言ShardingSphere的SQL解析,本篇文章源码基于4.0.1版本ShardingSphere的分片引擎从解析引擎到路由引擎到改写
- 线程安全当多个线程访问某个类时,不管运行时环境采用何种调度方式或者这些进程将如何交替执行,并且在主调代码中不需要任何额外的同步或协调,这个类
- 一、导言1.1 介绍桥接模式及其应用背景桥接模式(Bridge Pattern)是一种结构型设计模式,它将抽象部分与实现部分分离,使它们可以
- @Value注解读取yml中的map配置网上查了好多资料,都是.properties文件中读取,而且又是几个人抄来抄去,找了半天功夫不负有心
- 1,添加依赖在project的build.gradle文件中添加dependencies { classpath 'co
- 在任何Java面试当中多线程和并发方面的问题都是必不可少的一部分。如果你想获得任何股票投资银行的前台资讯职位,那么你应该准备很多关于多线程的
- 在Servlet2.5中,我们要实现文件上传功能时,一般都需要借助第三方开源组件,例如Apache的commons-fileupload组件
- 前言空间分配要点有:一是空间分配的连续性;二是动态内存申请;三是防止程序执行中出现异常错误。提示:开始讲解了嗷~后续会根据精力持续更新嗷!!
- 背景Java8的stream接口极大地减少了for循环写法的复杂性,stream提供了map/reduce/collect等一系列聚合接口,
- 有时候,我们需要制作一个Word模板文档,然后发给用户填写,但我们希望用户只能在指定位置填写内容,其他内容不允许编辑和修改。这时候我们就可以
- 在使用springMVC框架构建web应用,客户端常会请求字符串、整型、json等格式的数据,通常使用@ResponseBody注解使 co
- 1. 前言老板说,明天甲方要来看产品,你得造点数据,而且数据必须是“真”的,演示效果要好看一些,这样他才会买我们的产品,我好明年给你换个嫂子
- 前言 短时间提升自己最快的手段就是背面试题,最近总结了Java常用的面试题,分享给大家,希望大家都能圆梦大厂,加油,我命由我不由天
- 建造者模式针对的是复杂对象的构建,比如一个产品有多个部分构成,每个部分都可以单独进行生产,这时候就可以用建造者模式,由Builder构造产品