Java 数据结构之删除链表中重复的结点
作者:2021dragon 时间:2023-11-28 15:36:22
核心考点:链表操作,临界条件检查,特殊情况处理
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。
解析一:(不提倡)
解决该问题较简单,且在写代码时不易出错的做法如下:
遍历一遍链表,记录重复结点的结点值。
再遍历一遍链表,逐个删除重复结点。
动图演示:
该方法需要遍历两遍链表,且需要开辟额外的内存空间存储重复结点的结点值,所以一般不提倡。
/*
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
标签:Java,删除,链表,结点
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Mybatis-Plus的SQL语句组拼原理说明
2021-07-03 20:39:22
![](https://img.aspxhome.com/file/2023/5/84285_0s.png)
在Android系统中使用WebViewClient处理跳转URL的方法
2021-08-03 14:24:59
Java反射如何修改private final成员变量值
2023-09-06 03:43:18
使用C#编写15子游戏
2023-03-23 08:28:52
![](https://img.aspxhome.com/file/2023/3/129633_0s.png)
Java 添加、读取和删除 Excel 批注的操作代码
2023-10-28 21:55:36
![](https://img.aspxhome.com/file/2023/5/81885_0s.png)
JVM教程之内存管理和垃圾回收(三)
2023-11-10 15:49:54
![](https://img.aspxhome.com/file/2023/2/59352_0s.jpg)
SpringBoot项目jar和war打包部署方式详解
2023-05-10 14:58:29
详解Java编程中JavaMail API的使用
2022-08-02 06:18:23
springboot2.x整合tkmapper的示例代码
2021-09-19 11:56:59
Java锁的升级策略 偏向锁 轻量级锁 重量级锁
2022-11-07 00:50:17
![](https://img.aspxhome.com/file/2023/8/91078_0s.png)
C# 16进制与字符串、字节数组之间的转换
2021-07-13 08:08:10
nacos注册中心单节点ap架构源码解析(最新推荐)
2022-09-02 09:31:43
![](https://img.aspxhome.com/file/2023/6/98116_0s.png)
全面解析SpringBoot文件上传功能
2023-02-26 15:55:56
![](https://img.aspxhome.com/file/2023/2/67462_0s.png)
c# 在windows中操作IIS设置FTP服务器的示例
2023-07-18 06:13:01
![](https://img.aspxhome.com/file/2023/6/66116_0s.jpg)
Java ArrayList中存放引用数据类型的方式
2023-11-16 15:23:46
![](https://img.aspxhome.com/file/2023/6/60556_0s.png)
SpringBoot Scheduling定时任务的示例代码
2023-08-12 17:55:05
C#发送内置图片html格式邮件的方法
2021-11-14 08:07:42
Java 回调函数详解及使用
2023-11-03 02:32:35
mybatis查询语句揭秘之参数解析
2021-07-10 01:17:18
使用Thumbnails实现图片指定大小压缩
2021-11-14 11:07:34
![](https://img.aspxhome.com/file/2023/7/138267_0s.jpg)