83. Remove Duplicates from Sorted List

Easy

Given a sorted linked list, delete all duplicates such that each element appear only once.

😇 Solution

O(n)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:

        dummy = head
        while(head and head.next):
            if head.val == head.next.val:
                head.next = head.next.next
            else:
                head = head.next
        
        return dummy

O(n)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        
        if not head:
            return head
        
        l = []  
        while(head):
            if head.next:
                if head.val != head.next.val:
                    l.append(head)
            else:
                l.append(head)
            head = head.next
        i=0
        while(i < len(l)-1):
            l[i].next = l[i+1]
            i += 1
        l[i].next
        
        return l[0]

unsorted

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head
        
        dummy = ListNode(-1)
        dummy.next = head
        
        s = set()
        node = head
        while(node):
            s.add(node.val)
            node = node.next
        
        node = dummy
        while(node.next):
            if node.next.val not in s:
                node.next = node.next.next
            else:
                s.remove(node.next.val)
                node = node.next
        
        return dummy.next