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

Difficulty
Medium
Tags
链表
URL
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
Star
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
notion imagenotion image
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
notion imagenotion image
输入：head = [1,1,1,2,3]
输出：[2,3]
提示：
  • 链表中节点数目在范围 [0, 300] 内
  • 100 <= Node.val <= 100
  • 题目数据保证链表已经按升序 排列

法1

思路
把值相同的看做是一段，然后一段一段的往前走
每向前走一步，都回头看一下和之前的值是否一样：
如果和之前的值一样，那么标记之前的值需要删除
如果不一样，查看标记，如果未标记删除，那就把之前的节点接到我的最终结果上。
题解
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head

        dummy = ListNode(-1)
        res = dummy
        prev = head
        flag = False
        cur = prev.next
        while cur:
            # 当前和之前不同
            if cur.val != prev.val:
                # 之前的没用重复出现
                if flag is False:
                    res.next = ListNode(prev.val)
                    res = res.next  
                prev = cur
                flag = False
            # 当前和之前的相同
            else:
                flag = True
            cur = cur.next
        # 最后一个元素特判
        if flag is False:
            res.next = prev

        return dummy.next
上述的代码创建了一个新节点，其实可以不用创建新节点，只需要每次添加新节点之后，把后面的断开
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head

        dummy = ListNode(-200)
        # 双指针的思路，两个指针
        left = dummy
        prev, right = head, head.next

        length = 1
        while right:
            # 和之前的不一样，根据长度判断是否需要接上去
            if right.val != prev.val:
                if length == 1:
                    left.next = prev
                    left = left.next
                    left.next = None
                else:
                    length = 1
                prev = right
            else:
                length += 1
            
            right = right.next
        
        # 最后一个节点不能忘记
        if length == 1:
            left.next = prev

        return dummy.next