专栏首页蛮三刀的后端开发专栏[Leetcode][python]删除排序链表中的重复元素/删除排序链表中的重复元素 II

[Leetcode][python]删除排序链表中的重复元素/删除排序链表中的重复元素 II

Remove Duplicates from Sorted List

题目大意

删除一个有序链表中重复的元素,使得每个元素只出现一次。

解题思路

如果当前节点有后一个节点,且它们的值相等,那么当前节点指向后一个节点的下一个节点,这样就可以去掉重复的节点。

代码

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None or head.next == None:
            return head
        p = head
        while p.next:
            if p.next.val == p.val:
                p.next = p.next.next
            else:
                p = p.next
        return head

Remove Duplicates from Sorted List II

题目大意

把一个有序链表中所有重复的数字全部删光,删除后不再有原先重复的那些数字。

解题思路

不同的地方是这里要删掉所有的重复项,由于链表开头可能会有重复项,被删掉的话头指针会改变,而最终却还需要返回链表的头指针。

所以需要定义一个新的节点,然后链上原链表,然后定义一个前驱指针和一个现指针,每当前驱指针指向新建的节点,现指针从下一个位置开始往下遍历,遇到相同的则继续往下,直到遇到不同项时,把前驱指针的next指向下面那个不同的元素。如果现指针遍历的第一个元素就不相同,则把前驱指针向下移一位。

代码

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None:
            return head
        dummy = ListNode(-1)
        dummy.next = head
        p = dummy
        temp = head
        while p.next:
            while temp.next and temp.next.val == p.next.val:
                temp = temp.next
            if temp == p.next:  # 如果p.next temp相等,说明并没有重复,两个都进一位
                p = p.next
                temp = p.next
            else:  # 如果p.next和temp不相等,说明temp已经跑到很后面了(至少大两位),所以需要将p直接指向temp.next
                p.next = temp.next
        return dummy.next

总结

两个都是链表基础题,值得反复学习

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 单链表逆序

    第二个题目是很经典的“单链表逆序”问题。很多公司的面试题库中都有这道题,有的公司明确题目要求不能使用额外的节点存储空间,有的没有明确说明,但...

    后端技术漫谈
  • [Leetcode][python]Add Two Numbers/两数相加

    给定两个链表分别代表两个非负整数。数位以倒序存储,并且每一个节点包含一位数字。将两个数字相加并以链表形式返回。

    后端技术漫谈
  • [Leetcode][python]Swap Nodes in Pairs/两两交换链表中的节点

    交换链表中相邻的两个元素。 注意第一个节点与第二个节点要交换位置,而第二个节点不用与第三个节点交换位置。 注意点: 不允许修改节点的值 ...

    后端技术漫谈
  • 谷歌刷题打卡03-链表插入排序

    程序员小王
  • [数据结构与算法] 邂逅链表

    在我们的生活中, 最符合链表结构(准确的说是双链表)的物体的就是火车了(如下图). 我们在车厢内时,每次只能从本车厢到下一个车厢或者上一个车厢,如同对链表的遍...

    时间静止不是简史
  • 每日一题2-对链表进行插入排序

    输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->5

    程序员小王
  • python 实现线性链表(单链表)

    初学python,拿数据结构中的线性链表存储结构练练手,理论比较简单,直接上代码。

    py3study
  • 双向链表

    双向链表除头节点外,每个节点除data都有next和pre,next指向下一个节点的内存地址,pre指向上一个节点都内存地址,头节点,没有data,pre指向n...

    桑鱼
  • [剑指offer] 替换空格

    请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

    尾尾部落
  • 使用 XDebug + Webgrind 进行 PHP 程序性能分析

    因为 Profiler 生成的性能记录文件的格式,不是给人看的,所以需要 Webgrind 图形界面的分析工具

    cnguu

扫码关注云+社区

领取腾讯云代金券