Catalog

LeetCode_83： Delete duplicate elements from the sort list

One 、 subject

Two 、 Example

3、 ... and 、 Ideas

Four 、 Code

LeetCode_82： Delete duplicate elements from the sort list II

One 、 subject

Two 、 Example

3、 ... and 、 Ideas

Four 、 Code

LeetCode_83： Delete duplicate elements from the sort list

One 、 subject

Given a sorted linked list , Delete all duplicate elements , So that each element only appears once .

Two 、 Example

Example  1:

Input : 1->1->2
Output : 1->2

Example  2:

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

3、 ... and 、 Ideas

Simple violence law , The front and back pointers traverse the linked list once ,pre and cur Two hands, one before and one after .

If the values indicated by two pointers are equal , Delete cur The node pointed to by the pointer .

Four 、 Code

# 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： Delete duplicate elements from the sort list II

One 、 subject

There is one. in ascending order Arranged linked list , Give you the head node of this list head , Please delete all nodes with duplicate numbers in the linked list , Keep only the original list   No recurrence   The number of .

Returns a list of results in ascending order .

Two 、 Example

Example 1：

Input ：head = [1,2,3,3,4,4,5]
Output ：[1,2,5]

Example 2：

Input ：head = [1,1,1,2,3]
Output ：[2,3]

Tips ：

• The number of nodes in the linked list is in the range [0, 300] Inside
• -100 <= Node.val <= 100
• The title data ensures that the linked list has been arranged in ascending order

3、 ... and 、 Ideas

Simple and crude method :

First traversal , Count the numbers in the linked list , If the number of times is greater than 1, That is, the repeated numbers , Deposit it in list repeated in .

Second traversal , Is to delete duplicate numbers , If the current number is a repeating number , It will appear in list repeated in , Delete it now .

Four 、 Code

# 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

        #  Duplicate node 
        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)

        #  Delete operation 
        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