专栏首页Rude3Knife的后端开发专栏[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 条评论
登录 后参与评论

相关文章

  • POJ 1410--Intersection(判断线段和矩形相交)

    Intersection Time Limit: 1000MS Memory Limit: 10000K Total Submissions:...

    Enterprise_
  • 2018 Wannafly summer camp Day3--Travel

    Travel 描述 题目描述: 魔方国有n座城市,编号为1∼n1∼n1\sim n。城市之间通过n-1条无向道路连接,形成一个树形结构。

    Enterprise_
  • C#脚本实践(四): 反射与序列化

    逍遥剑客
  • atan和atan2反正切计算

    返回值 若不出现错误,则返回 arg 在[−π/2;+π/2][−π/2;+π/2] [- π/2 ; +π/2] 弧度范围中的弧(反)正切( arctan...

    Enterprise_
  • HDU 6354--Everything Has Changed(判断两圆关系+弧长计算)

    Enterprise_
  • 从问题到探索--从slice说起

    如果你是新手,你发现你对于别人说的一切都表示有疑问,那么恭喜你!你拥有大部分编程老手已经遗忘的能力——对细节的敏感。善于发现问题是一个很好的习惯,接触的东西多了...

    the5fire
  • 由__future__中unicode_literals引起的错误来研究python中的编码问题

    在py2.7的项目中用了future模块中的 unicode_literals 来为兼容py3.x做准备,今天遇到一个UnicodeEncodeError的错误...

    the5fire
  • 2018 Wannafly summer camp Day3--Knight

    Knight 题目描述: 有一张无限大的棋盘,你要将马从(0,0)(0,0)(0,0)移到(n,m)(n,m)(n,m)。 每一步中,如果马在(x,...

    Enterprise_
  • HDU 6330--Visual Cube(构造,计算)

    Enterprise_
  • POJ 1113--Wall(计算凸包)

    Wall Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 40363 ...

    Enterprise_

扫码关注云+社区

领取腾讯云代金券