当前位置：网站首页>LeetCode83 ＆＆ LeetCode82：删除排序链表中的重复元素

# 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:
        """
        :param head:
        :return:
        """
        if not head or not head.next:
            return head
        pre, cur = head, head.next
        while pre and cur:
            if pre.val == cur.val:
                pre.next = cur.next
                cur = cur.next
            else:
                pre = pre.next
                cur = cur.next
        return head

if __name__ == '__main__':
    head = ListNode(1)
    head.next = ListNode(1)
    head.next.next = ListNode(1)
    head.next.next.next = ListNode(2)
    head.next.next.next.next = ListNode(3)
    s = Solution()
    ans = s.deleteDuplicates(head)

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

一、题目

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。

返回同样按升序排列的结果链表。

二、示例

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

三、思路

简单粗暴法:

第一次遍历，将链表中的出现过的数字进行计数，若次数大于1，即为重复出现的数字，将其存入列表 repeated 中。

第二次遍历，则是删除重复数字，当前数字若为重复数字，便会出现在列表 repeated 中，此时进行删除即可。

四、代码

# 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):
        """
        :param head: ListNode
        :return: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        nums = dict()
        node = head

        # 重复的节点
        repeated = []

        while node:
            if node.val not in nums:
                nums[node.val] = 1
            else:
                nums[node.val] += 1
                if node.val not in repeated:
                    repeated.append(node.val)
            node = node.next
        # print(nums)
        # print(repeated)

        # 删除操作
        pre, cur = dummy, head
        # pre = dummy
        while cur:
            if cur.val in repeated:
                pre.next = cur.next
                cur = cur.next
            else:
                pre = pre.next
                cur = cur.next

        return dummy.next

if __name__ == '__main__':
    head = ListNode(1)
    head.next = ListNode(1)
    head.next.next = ListNode(1)
    head.next.next.next = ListNode(2)
    head.next.next.next.next = ListNode(3)
    s = Solution()
    ans = s.deleteDuplicates(head)
    # 1->1->1->2->3

原网站

版权声明
本文为[柠檬不甜会酸]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_45666660/article/details/115203139