湖南省住房和城乡建设厅门户网站,做网站 域名如何要回,网站开发平台 运行平台,惠州市网站开发删除链表中重复的结点 题目描述在一个排序的链表中#xff0c;存在重复的结点#xff0c;请删除该链表中重复的结点#xff0c;重复的结点不保留#xff0c;返回链表头指针。 例如#xff0c;链表1-2-3-3-4-4-5 处理后为 1-2-5写链表中我…删除链表中重复的结点 题目描述在一个排序的链表中存在重复的结点请删除该链表中重复的结点重复的结点不保留返回链表头指针。 例如链表1-2-3-3-4-4-5 处理后为 1-2-5写链表中我们知道对于单链表访问最大的缺点就是只能单向从前向后所以我们删除也是一样删除当前就得知道当前的上一个节点那么我们这里采用指针记录的方式。方法1粗暴我们采用最容易想到的方法不用考虑时间效率与空间效率问题就直接用遍历用一个哈希表结构来记录每个节点对应的值在节点中出现了几次统计完成后然后通过哈希表中如果出现次数为大于等于2再用两个指针一个前一个后开始找对应的值就行了如果后一个指针指向的节点的值为哈希表中出现次数大于等于2的数那么前一个指针指向后一个指针的next然后删除后一个指针所指向的节点让后一个指针重新指向前一个指针的next就这样就可以完成删除。虽然这个方法可以但是时间复杂度为O(N) 空间复杂度为一个哈希表的结构所以采用这种不是最佳选择。方法2三指针法采用三个指针来进行遍历同时删除重复的节点因为是有序的链表我们就可以确定重复的元素肯定是在一块链接所以我们就可以用三指针我们这里就叫 pre、cur、nex 分别代表的是前中后三个指针我们在考虑的情况中如果头节点开始就重复我们就处理很起来多了一种情况就需要额外处理所以我们添加一个头节点变成带头节点保证了头节点开始不会重复那么我们就可以让开头是pre指向带头的节点cur指向pre的nextnex指向cur的next。接下来我们就可以看cur是否和nex相等相等就让nex继续向下走不相等然后再处理删除cur开始到nex中间节点都是要删除的包含cur指向不包含nex指向删除就用到了pre删除完成让pre指向cur就可以了。如果cur值与nex值不相等那么就可以三个指针各自往前移动一个。注在实现时自己添加一个头结点把头结点链接到链表上方便。
