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

xiaoxiao2021-02-28  8

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

总结

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

后端技术漫谈 认证博客专家 分布式 Linux Java 我是一名后端开发工程师。主要关注后端开发,数据安全,爬虫,物联网,边缘计算等方向,欢迎交流。各大平台都可以找到我:- 微信公众号:后端技术漫谈- Github:@qqxx6661- :@蛮三刀把刀- 知乎:@后端技术漫谈- 简书:@蛮三刀把刀- 掘金:@蛮三刀把刀- 腾讯云+社区:@后端技术漫谈原创文章主要内容:- 后端开发- Java面试- 设计模式/数据结构/算法题解- 爬虫/边缘计算/物联网- 读书笔记/逸闻趣事/程序人生
转载请注明原文地址: https://www.6miu.com/read-2000022.html

最新回复(0)