每日一道算法之--删除排序链表中的重复元素 II

链表

Word count: 469Reading time: 1 min

 2020/04/10   Share

删除排序链表中的重复元素 II

力扣第82题: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:

输入: 1->1->1->2->3
输出: 2->3

滑动窗口思想

读完了这道题目,注意一个点,就是只要是重复元素,就要删掉所有,而且链表是排序的,也就是说重复元素肯定是连在一起的。所以我的思路如下：

首先定义两个指针，一个指向为重复元素的前一个元素，称为left，这样做的原因是因为如果遍历链表在去判断的话，一旦碰到这一块重复元素，还需要在去遍历一次获取他们的前一个元素，才能将他们去除，所以我直接就定义一个指针。另一个就是left指针的下一个元素，用来寻找重复的元素。
定义一个count变量，初始值为0，用来记录是否是重复元素，如果count为0，则不是，否则就是重复元素。
因为链表头也可能是重复元素,所以要给链表添加一个边界头.

# 思路有点像滑动指针
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        new_head = ListNode(-1)
        new_head.next = head
        left = new_head
        while left and left.next:
            right = left.next
            count = 0
            # right指针移动
            while right.next and right.val == right.next.val:
                right = right.next
                count += 1
            # 证明是right指针重复元素
            if count != 0:
                right = right.next
            # 删除重复的元素
            left.next = right
            if count == 0:
                # right指针不是重复元素,则需要将left移动一个单位
                left = left.next
        return new_head.next

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/04/10/algorithm-82/

发表日期：April 10th 2020, 4:40:53 pm

更新日期：April 10th 2020, 4:43:55 pm

Next Post

每日一道算法之--杨辉三角
Previous Post

每日一道算法之--颜色分类

CATALOG

1. 删除排序链表中的重复元素 II
1. 1.1. 滑动窗口思想

