LeetCode 82. Remove Duplicates from Sorted List II

简介: 给定已排序的链接列表,删除所有具有重复数字的节点,只留下原始列表中的不同数字。

v2-1b3d762824b37428823ae260ffdafa0f_1440w.jpg


Description



Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.


Example 1:

Input: 1->2->3->3->4->4->5

Output: 1->2->5


Example 2:

Input: 1->1->1->2->3

Output: 2->3


描述



给定已排序的链接列表,删除所有具有重复数字的节点,只留下原始列表中的不同数字。


思路



  • 这道题要求删除已排序链表中所有重复的元素.
  • 我们用两个指针,pre,point.pre指向第一个元素,point指向第二个元素.
  • 当point指向的值和point指向的下一个元素的值相同的时,删除下一个元素,如此重复.最后阐述point本身,point指向下一个元素.
  • 有如下特殊情况需要注意:
  • 头节点如果重复,头节点是不会在循环中删除的.
  • 当链表中只有两个元素且相同时,或者有不止两个元素,前两个元素相同,但与第三个元素不同:此时前两个元素不会被删除,需要另外删除.


# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2018-12-23 17:06:54
# @Last Modified by:   何睿
# @Last Modified time: 2018-12-23 19:49:13
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        isclear, pre, point = False, head, head.next
        if head.val == head.next.val:
            # 记录头节点是否重复
            isclear = True
        while point and point.next:
            # 用于记录当前值是否需要清除
            if point.val == point.next.val:
                # 清除point后面所有和point相同值的元素
                while point.next and point.val == point.next.val:
                    # 指向需要删除的节点
                    temp = point.next
                    # 删除该节点
                    point.next = temp.next
                    temp.next = None
                # 清除point元素本身
                # pre的nexe指针指向point后面一个元素
                pre.next = point.next
                # point指向下一个元素
                point = point.next
                continue
            point = point.next
            pre = pre.next
        # 如果序列第一个元素和第二个元素相等,去掉这两个元素
        # 在上面的循环中,如果只有两个元素或者第三个元素与第二个元素不等,
        # 都会导致前两个相同的元素不被删除
        if head and head.next and head.val == head.next.val:
            return head.next.next
        # 在上面的循环中,如果第一个出现了重复,且重复次数超过2(即至少前三个元素相同)
        # 会把第一个元素后面重复的元素删除,其本身不会被删除
        elif isclear:
            # 如果进入到了这里,说明头节点重复,头节点后面等于头节点的所有元素已被删除.
            # 但是头节点本身并没有被删除.
            return head.next
        # 其他情况,直接返回head
        else:
            return head
if __name__ == "__main__":
    a = ListNode(1)
    b = ListNode(1)
    a.next = b
    c = ListNode(2)
    b.next = c
    c.next = None
    so = Solution()
    res = so.deleteDuplicates(a)
    head = res
    while head:
        print(head.val)
        head = head.next


源代码文件在这里.

目录
相关文章
Leetcode 19.Remove Nth Node From End of List
删除单链表中的倒数第n个节点,链表中删除节点很简单,但这道题你得先知道要删除哪个节点。在我的解法中,我先采用计数的方式来确定删除第几个节点。另外我在头节点之前额外加了一个节点,这样是为了把删除头节点的特殊情况转换为一般情况,代码如下。
36 0
|
27天前
|
存储 分布式计算 NoSQL
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
24 3
|
3月前
|
存储 NoSQL 算法
Redis6入门到实战------ 三、常用五大数据类型(列表(List)、集合(Set)、哈希(Hash)、Zset(sorted set))
这是关于Redis 6入门到实战的文章,具体内容涉及Redis的五大数据类型:列表(List)、集合(Set)、哈希(Hash)、有序集合(Zset(sorted set))。文章详细介绍了这些数据类型的特点、常用命令以及它们背后的数据结构。如果您有任何关于Redis的具体问题或需要进一步的帮助,请随时告诉我。
|
6月前
使用List中的remove方法遇到数组越界
使用List中的remove方法遇到数组越界
95 2
|
6月前
List中的remove方法遇到报错不能删除以及四种解决办法点赞收藏
List中的remove方法遇到报错不能删除以及四种解决办法点赞收藏
235 0
|
6月前
|
大数据 Java 程序员
「LeetCode合集」链表(List)及经典问题
「LeetCode合集」链表(List)及经典问题
49 0
|
12月前
避免list中remove导致ConcurrentModificationException
避免list中remove导致ConcurrentModificationException
43 0
Leetcode 4. Median of Two Sorted Arrays
题目描述很简单,就是找到两个有序数组合并后的中位数,要求时间复杂度O(log (m+n))。 如果不要去时间复杂度,很容易就想到了归并排序,归并排序的时间复杂度是O(m+n),空间复杂度也是O(m+n),不满足题目要求,其实我开始也不知道怎么做,后来看了别人的博客才知道有个二分法求两个有序数组中第k大数的方法。
38 0
|
5月前
|
安全 Java
java线程之List集合并发安全问题及解决方案
java线程之List集合并发安全问题及解决方案
838 1
|
4月前
|
Java API Apache
怎么在在 Java 中对List进行分区
本文介绍了如何将列表拆分为给定大小的子列表。尽管标准Java集合API未直接支持此功能,但Guava和Apache Commons Collections提供了相关API。