专栏首页灰子学技术算法篇:链表之删除链表中重复节点

算法篇:链表之删除链表中重复节点

算法:

核心点在于如何找到重复节点,有序链表的话,只要下一个节点与当前节点数值一样就是重复节点,直接将当前节点指向下一个节点的下一个节点即可。

本算法需要注意哨兵节点的小技巧。

题目1:删除排序链表中的重复元素 https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/submissions/

代码实现:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    curr := head
    for curr != nil && curr.Next != nil  {
        
        if curr.Val == curr.Next.Val { // 删除重复节点,node
            tmp := curr.Next
            curr.Next = tmp.Next
        } else { // 不是重复节点的话,移动节点
            curr = curr.Next
        }
    
    }
    return head
}

执行结果:

题目2: 删除排序链表中的重复元素

代码实现

// 算法:与题目1的不同之处在于,本题目是删除所有重复的节点,
// 也就是说不单单要找到重复节点的位置,
// 还需要将第一个重复节点的前一个节点记录下来,这里叫做pre
// 然后通过pre.Next去指向重复节点的后面哪一个不重复的节点,来完成删除。
// 涉及到前序节点pre,就需要考虑哨兵节点。
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    n := new(ListNode) // 设置钩子节点,避免头节点都被删除不好操作
    n.Next = head
    pre := n
    for pre != nil { // pre是当前节点的前一个节点
        if pre.Next == nil {
            break
        }

        curr := pre.Next
        next := curr.Next
        for next != nil { // 比较重复的节点
            if next.Val != curr.Val {
                break
            }
            next = next.Next
        }

        if curr.Next == next { 
            pre = pre.Next
        } else { // 重复的,删除重复节点
            pre.Next = next
        }
    }
    return n.Next
}

执行结果:

本文分享自微信公众号 - 灰子学技术(huizixueguoxue),作者:灰子学技术

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法篇:链表之反转链表

    https://leetcode-cn.com/problems/reverse-linked-list/

    灰子学技术
  • 算法篇:链表之合并有序链表

    算法的核心在于两个有序链表的合并操作,K个有序链表的合并只是一个变形题目,先拆分成k/2个有序链表,然后等比数列减少到1个数列。

    灰子学技术
  • 算法篇:链表之删除和为0的元素

    利用前缀和的方法,例如前缀和[3,5,6,3,7],那么第一个3和最后一个3之间的节点之和就是0,不然的这两个数字不可能相等

    灰子学技术
  • 数据结构与算法-二叉树(二)

    二叉查找树是一种特殊的二叉树,它支持动态的数据集合的快速插入、删除和查找操作。二叉查找树的一般结构如下图所示:

    用户3470542
  • 什么是二叉搜索树

    二叉搜索树是一种综合效率比较好的一种数据结构,搜索、插入、删除的复杂度等于树高, 平均空间复杂度为O(n),时间复杂度为O(log n),最坏时间复杂度为O(n...

    我是攻城师
  • 真的,千万不要给女朋友解释 什么是 “羊群效应”

    媳妇最近突然爱学习了,各种刷算法、架构方面的题,没日没夜的带娃还有这个劲头,着实让我没想到。看似一片欣欣向荣,不过,长期的生存经验告诉我,这并不是什么好事,事出...

    程序员内点事
  • 千万不要给女朋友解释 什么是 “羊群效应”

    媳妇最近突然爱学习了,各种刷算法、架构方面的题,没日没夜的带娃还有这个劲头,着实让我没想到。看似一片欣欣向荣,不过,长期的生存经验告诉我,这并不是什么好事,事出...

    程序员内点事
  • CDN边缘节点计算策略

    本文来自CONTENT DELIVERY SUMMIT的演讲,演讲者是来自Limelight Networks公司Edge Strategy & Solutio...

    用户1324186
  • 后缀自动机经典操作

    attack
  • 我们在外包资源池化管理走过的弯路

    品质中心近半年提出了外包人员效率优化的口号。各个测试团队积极响应,想出各种各样的办法来尝试节省人力。其中“外包资源池管理”是各个团队都没有放过的一种尝试手段。

    腾讯移动品质中心TMQ

扫码关注云+社区

领取腾讯云代金券