剑指offer：删除该链表中重复的结点

2024-08-24 00:38
文章标签 链表 删除 重复 offer 结点

本文主要是介绍剑指offer：删除该链表中重复的结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

思路：

设置三个指针，pre，curr，next。curr代表当前节点，pre代表前一节点，next代表后一节点，思路是每次如果next与curr的值相等，就将next后移直到next指向第一个与curr值不相等的节点，直接令pre->next=next，这样就将curr到next之间重复发节点全部删除了。重点是要特别注意删除头结点的情况。

初始时curr指向头结点，next指向下一节点，如果next和curr的值不相等，就令pre=curr，curr=pre->next。如果next和curr的值相等，就将next往后移一位，一直到next的值与curr的值不相等。此时如果curr是头结点，就重新设置头结点为next指向的节点，curr=next；如果不是头结点，就令pre->next=next，curr=pre->next。

特别注意：

在一切有->next操作的地方都要先确保当前节点不为空。

在判断相等的时候，不能直接判断节点，而是判断value，因为next指针不同。

参考代码：

在线测试

https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&tqId=11209&rp=3&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=3

AC代码

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead){if(pHead==NULL||pHead->next==NULL)return pHead;ListNode* curr=pHead;ListNode* pnext;ListNode* pre;while(curr!=NULL){pnext=curr->next;if(pnext!=NULL&&pnext->val==curr->val){pnext=pnext->next;while(pnext!=NULL&&pnext->val==curr->val){pnext=pnext->next;}if(curr==pHead)pHead=pnext;elsepre->next=pnext;curr=pnext;}else{pre=curr;curr=pre->next;}}return pHead;}
};

 

越界？特别注意在一切有->next操作的地方都要先确保当前节点不为空。修改之后还是不对，因为pHead重复的情况应该放在循环里面处理，不应该只单独处理一次。会出现测试用例:{1,1,2,2,3,3,4,4}

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead){if(pHead==NULL||pHead->next==NULL)return pHead;ListNode* curr=pHead;ListNode* pnext=pHead->next;if(pnext->val==curr->val){while(pnext!=NULL && pnext->val==curr->val){pnext=pnext->next;}pHead=pnext;}if(pHead==NULL||pHead->next==NULL)return pHead;ListNode* pre=pHead;curr=pre->next;while(curr!=NULL&&curr->next!=NULL){pnext=curr->next;if(pnext->val==curr->val){//pnext=pnext->next;while(pnext!=NULL&&pnext->val==curr->val){pnext=pnext->next;}pre->next=pnext;}elsepre=curr;curr=pre->next;}return pHead;}
};

之前理解错题意，以为将有重复的元素还保留下来，输出1->2->3->4->5。代码如下：要特别注意如果pNode=NULL，就不能再做->next的操作了，不然会越界报错，所以while里面除了有两个越界检查条件。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead){if(pHead==NULL||pHead->next==NULL)return pHead;ListNode* pNode=pHead;while(pNode!=NULL&&pNode->next!=NULL){while(pNode!=NULL&&pNode->next!=NULL&&pNode->next->val==pNode->val){ListNode* temp=pNode->next;pNode->next=temp->next;}pNode=pNode->next;}return pHead;}
};

上面两个AC版本分别对应leetcode82和83

leetcode 82 AC代码如下

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if(head==NULL||head->next==NULL)return head;ListNode* pre=NULL;ListNode* curr=head;ListNode* pnext=NULL;while(curr!=NULL){pnext=curr->next;if(pnext!=NULL&&pnext->val==curr->val){while(pnext!=NULL&&pnext->val==curr->val){pnext=pnext->next;}if(curr==head){head=pnext;curr=pnext;}else{pre->next=pnext;curr=pnext;}}else{pre=curr;curr=pnext;}}return head;}
};

 

这篇关于剑指offer：删除该链表中重复的结点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1100957。

相关文章

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C
阅读更多...
poj2406（连续重复子串）

poj2406（连续重复子串）

题意:判断串s是不是str^n，求str的最大长度。 解题思路：kmp可解，后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后，自动跳转到next[i]，所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下； #include<iostream>#include<algorithm>#include<stdio.h>#include<math.
阅读更多...
poj3261（可重复k次的最长子串）

poj3261（可重复k次的最长子串）

题意：可重复k次的最长子串 解题思路：求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N，但实际复杂度很低。题目数据也比较水，不然估计过不了。 代码入下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
pip-tools：打造可重复、可控的 Python 开发环境，解决依赖关系，让代码更稳定

pip-tools：打造可重复、可控的 Python 开发环境，解决依赖关系，让代码更稳定

在 Python 开发中，管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等，都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools？ pip-tools 是一组命令行工具，旨在简化 Python 依赖关系的管理，确保项目环境的稳定性和可重复性。它主要包含两个核心工具：pip-compile 和 pip
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
C# 防止按钮botton重复“点击”的方法

C# 防止按钮botton重复“点击”的方法

在使用C#的按钮控件的时候，经常我们想如果出现了多次点击的时候只让其在执行的时候只响应一次。这个时候很多人可能会想到使用Enable=false, 但是实际情况是还是会被多次触发，因为C#采用的是消息队列机制，这个时候我们只需要在Enable = true 之前加一句 Application.DoEvents();就能达到防止重复点击的问题。 private void btnGenerateSh
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2