剑指offer 面试题 删除链表中重复的节点
2024-09-06 20:42:05
题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
写法1：
当前遍历到cur节点，如果cur->next和cur->next->next的值相同，说明找到了重复节点，然后新建一个指针nex，一直往后找，直到值不等于之前重复节点的val值。将cur和nex连起来即可。
如1，2，2，2，3
cur遍历到1，此时cur之后的两个节点都为2，那么nex一路往后找到3，将1和3连起来，这样就删除了所有值为2的节点。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
auto dummy=new ListNode(INT_MIN);
dummy->next=pHead;
auto cur=dummy;
while(cur->next and cur->next->next){
if(cur->next->val==cur->next->next->val){
auto nex=cur->next;
int temp=cur->next->val;
while(nex and nex->val==temp){
nex=nex->next;
}
cur->next=nex;
}
else{
cur=cur->next;
}
}
return dummy->next;
}
};
写法2：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
auto dummy=new ListNode(INT_MIN);
dummy->next=pHead;
auto final_unique=dummy,cur=pHead,pre=dummy;
while(cur){
if(cur->next and cur->val==cur->next->val){
while(cur->next and cur->val==cur->next->val){
cur=cur->next;
}
//此时cur为最后一个重复节点
}
else{
final_unique->next=cur;
final_unique=cur;
}
cur=cur->next;
}
final_unique->next=nullptr;
return dummy->next;
}
};
最新文章
- Android—9.png的制作和去除黑线
- android 开发中 添加库文件 和so 文件的存放位置和添加依赖
- iOS保存cookie的方法
- ubuntu下sublime中文无法输入的问题
- python平台跨平台开发
- 18.1---不用加号的加法（CC150）
- Prim算法和Kruskal算法（图论中的最小生成树算法）
- 谈谈如何在面试中发掘程序猿的核心竞争力zz
- ChesFrame框架介绍
- Redis Install
- 所谓has a 和 is a
- Font Awesome 4.0.3 字体图标完美兼容IE7
- 入门git
- 开源Asp.Net MVC网上商城BrnShop
- File类和时间类的两道综合练习
- c#缓存技术(Dictionary)
- .net简介（一）
- Swift之Swift编码规范
- Go的Get命令兼容公司Gitlab仓库的HTTP协议
- Koa 学习笔记