【刷题日记】82. 删除排序链表中的重复元素 II

简介: 本次刷题日记的第 105 篇,力扣题为:82. 删除排序链表中的重复元素 II

本次刷题日记的第 105 篇,力扣题为:82. 删除排序链表中的重复元素 II

一、题目描述:

继续来做咱们的刷题试炼,删除排序链表中的重复元素 II

image.png

二、这道题考察了什么思想?你的思路是什么?

题目字数不多,表达的意思相当明确,本题要求我们删除链表中数值重复的所有节点,而不仅仅是删除重复多的节点

分析

根据题目要求,第一咱们需要考虑如何去找到数值重复的节点

第二我们需要考虑我们删除节点的位置,这个待删除的节点若是链表头,链表中间,链表尾巴的时候,我们需要如何抠掉我们要删除的节点,且还能让其他未被删除的节点正常连接

找到重复的节点这个简单,题目说明了这个链表是排序过的,因此咱们直接遍历链表,判断当前节点的数值是否和下一个节点的数值相等即可,若相等,则继续往下偏移是否再下一个节点也是相等的,直到找到第一个不相等的节点为止

例如题目中给出的示例 :head = [1, 1, 1, 2, 3]

image.png

如果第一个节点为头节点,那么咱们很明显最终头结点要偏移到数值为 2 的节点上面来

image.png

那这个时候其实我们就要为这种需要不断删除头结点的情况来做判断了,我们也可以使用简单高效的方式,那就是咱们可以定义一个假的头结点,例如这样

image.png

那么这个时候咱们就不用考虑头结点的事情了因为 头结点是永远不会被删除的,咱们直接按照逻辑去找相同的节点,找到挨着的最后一个相同的节点后,便将 Fake 节点的 next 指针指向下一个不同值的节点即可,例如这样

image.png

这个时候,咱们直接返回 Fake 节点的 next 即可

那么,接下来,咱们就来开心的撸代码吧

三、编码

根据上述逻辑和分析,我们就可以翻译成如下代码

  • 定义一个 Fake 节点指向链表头,做一个假的头结点
  • 遍历链表,找到重复的节点后,将 Fake 指针指向下一个节点,然后继续遍历,使用同样的方式进行处理即可

编码如下:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    dummy := &ListNode{0, head}
    cur := dummy
    for cur.Next != nil && cur.Next.Next != nil {
        if cur.Next.Val == cur.Next.Next.Val {
            x := cur.Next.Val
            for cur.Next != nil && cur.Next.Val == x {
                cur.Next = cur.Next.Next
            }
        } else {
            cur = cur.Next
        }
    }
    return dummy.Next
}

四、总结:

image.png

本次的这种实现方式比较讨巧,咱们引入了一个哑结点,咱们直接去遍历题目给出的链表就可以了,都不用考虑重复的元素是在链表头,链表中和链表尾巴,因此咱们的时间复杂度是 O(n)

空间复杂度是 O(1) ,咱们引入的都是常熟级别的空间消耗

原题地址:82. 删除排序链表中的重复元素 II

今天就到这里,学习所得,若有偏差,还请斧正

欢迎点赞,关注,收藏

朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力

image.png

好了,本次就到这里

技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。

我是阿兵云原生,欢迎点赞关注收藏,下次见~


相关文章
|
2月前
|
程序员
【刷题记录】移除链表元素
【刷题记录】移除链表元素
|
11天前
01_移除链表元素
01_移除链表元素
|
2月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
2月前
|
存储 C语言
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
|
2月前
【刷题记录】链表的回文结构
【刷题记录】链表的回文结构
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
44 5
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
34 4
|
2月前
|
机器学习/深度学习
【刷题记录】相交链表
【刷题记录】相交链表
|
2月前
【刷题记录】链表的中间结点
【刷题记录】链表的中间结点
|
2月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
22 0