Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:


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


Example 2:


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

Difficulty: interview

Starter 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:
        

Solutions:
# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def deleteDuplicates(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         if not head or not head.next:
             return head
         fakehead = ListNode(0)
         fakehead.next = head
         prev = fakehead
         slow = head
         fast = head.next
         while fast:
             if fast.val == slow.val:
                 while fast and fast.val == slow.val:
                     fast = fast.next
                 slow = prev
             else:
                 prev = slow
                 slow = slow.next
                 slow.val = fast.val
                 fast = fast.next
         slow.next = None
         return fakehead.next
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None
 
 class Solution(object):
     def deleteDuplicates(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         #start from nothing so we don't need to invalidate our position later
         real_head = ListNode(0)
         #previous also points to nothing at the start
         previous, current = real_head, head
         while current:
             #validate current.next OTHERWISE IT CRAHES DUMMY
             if current.next and current.next.val == current.val:
                 #remove ALL of the value in a tight loop
                 val_remove = current.val;
                 while current and current.val == val_remove:
                     current = current.next
                 previous.next = current
             else:
                 previous.next = current
                 previous = current
                 current = current.next
         return real_head.next
             
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None
 
 class Solution(object):
     def deleteDuplicates(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         #start from nothing so we don't need to invalidate our position later
         real_head = ListNode(0)
         #previous also points to nothing at the start
         previous, current = real_head, head
         while current:
             #validate current.next OTHERWISE IT CRAHES DUMMY
             if current.next and current.next.val == current.val:
                 #remove ALL of the value in a tight loop
                 val_remove = current.val;
                 while current and current.val == val_remove:
                     current = current.next
                 previous.next = current
             else:
                 previous.next = current
                 previous = current
                 current = current.next
         return real_head.next
             
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def deleteDuplicates(self, head):
         if head == None or head.next == None:
             return head 
        
         def get_next(node):
             while node != None and node.next != None and node.val == node.next.val:
                 cur_val = node.val
                 node = node.next.next
                 while node != None and node.val == cur_val:
                     node = node.next
             return node
 
         head = get_next(head)
         if head == None:
             return []
         
         prev = head
         cur = prev.next
         while (cur != None):
             cur = get_next(cur)
             prev.next = cur
             prev = cur
             if cur != None:
                 cur = cur.next
 
         return head
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def deleteDuplicates(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         dummy = ListNode(0)
         new_head = dummy
         prev = None
         n = 0
         while head:
             if prev is None:
                 prev = head
                 n = 1
             elif head.val != prev.val:
                 if n < 2:
                     new_head.next = prev
                     new_head = prev
                 prev = head
                 n = 1
             else:
                 n += 1
 
             head = head.next
         if n == 1:
             new_head.next = prev
             new_head = new_head.next
         new_head.next = None
         return dummy.next
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 
         #"""
         #:type head: ListNode
         #:rtype: ListNode
         #"""
 
 class Solution:  
     # @param head, a ListNode  
     # @return a ListNode  
     def deleteDuplicates(self, head):
         pre = ListNode(0)
         dummy = pre
         dummy.next = head
         while head and head.next:
             if head.val == head.next.val:
                 while head and head.next and head.val == head.next.val:
                     head = head.next
                 head = head.next
                 pre.next = head
             else:
                 pre = pre.next
                 head = head.next
         return dummy.next

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def deleteDuplicates(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         t = None
         c = None
         while head:
             if c is None or c != head.val:
                 t, head.next, head = head, t, head.next
                 c = t.val
             else:
                 while t and t.val == c:
                     t = t.next
                 head = head.next
         res = None
         while t:
             res, t.next, t = t, res, t.next
         return res

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def deleteDuplicates(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         dummy = ListNode(0)
         dummy.next = head
         node = dummy
         while node.next:
             next = node.next
             val = next.val
             if next.next and next.next.val == val:
                 next = next.next.next
                 while next and next.val == val:
                     next = next.next
                 node.next = next
             else:
                 node = node.next
         return dummy.next

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def deleteDuplicates(self, head):
         temp = head
         res = None
         resHead = None
         counter = 0
 
         while temp != None:
             counter = counter + 1
             if temp.next != None and temp.val == (temp.next).val:
                 duplicateval = temp.val
                 print("Duplicate Val: %d" % duplicateval)
 
                 # Iterate through the list till the value of duplicate are ongoing
                 while temp != None and temp.val == duplicateval:
                     temp = temp.next
             else:
                 if res == None:
                     res = ListNode(0)
                     res.val = temp.val
                     res.next = None
                     resHead = res
                 else:
                     res = resHead
                     while res.next != None:
                         res = res.next
                     
                     res.next = ListNode(0)
                     (res.next).val = temp.val
                     (res.next).next = None
             
                 temp = temp.next
                 #print("Next: %d", temp.val)
             
         return resHead

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def deleteDuplicates(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         if head == None:
             return None
         
         loop = head
         loop1 = head
         d = {}
         
         while loop:
             if loop.val in d.keys():
                 d[loop.val] += 1
             else:
                 d[loop.val] = 1
             loop = loop.next
         
         while loop1.next:
             if d[loop1.next.val] > 1:
                 loop1.next = loop1.next.next
             else:
                 loop1 = loop1.next
                 
         if d[head.val] > 1:
             return head.next
         else:
             return head
                 
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 from collections import OrderedDict
 
 class Solution:
     def deleteDuplicates(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         lookup = OrderedDict()
         
         while head:
             if head.val in lookup:
                 lookup[head.val] += 1
             else:
                 lookup[head.val] = 1
             head = head.next
         
         previous = None
         head = None
         for key in lookup:
             
             if (lookup[key] != 1):
                 continue
                 
             node = ListNode(key)
             if previous:
                 previous.next = node
             else:
                 head = node
             previous = node
 
         return(head)
         
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def deleteDuplicates(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         if head == None:
             return None
         
         loop = head
         loop1 = head
         d = {}
         
         while loop:
             if loop.val in d.keys():
                 d[loop.val] += 1
             else:
                 d[loop.val] = 1
             loop = loop.next
         
         while loop1.next:
             if d[loop1.next.val] > 1:
                 loop1.next = loop1.next.next
             else:
                 loop1 = loop1.next
                 
         if d[head.val] > 1:
             return head.next
         else:
             return head
                 
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def deleteDuplicates(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         if not head or not head.next:
             return head
         
         res = ListNode(0)
         p = res        
         cnt = 0
         while head:
             if cnt == 0:
                 candidate = head.val
                 cnt += 1
             elif candidate != head.val:
                 if cnt == 1:
                     p.next = ListNode(candidate)
                     p = p.next
                 candidate = head.val
                 cnt = 1
             else: 
                 cnt += 1
             head = head.next
         
         if cnt == 1:
             p.next = ListNode(candidate)
         return res.next
                 
             

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def deleteDuplicates(self, head):
         """
         :type head: ListNode
         :rtype: ListNode
         """
         if head is None or head.next is None:
             return head
         dmy = ListNode (head.val - 1)
         dmy.next = head
         prev = dmy
         curr = dmy
         dul = dmy.val
         while curr:
             if curr.val == dul:
                 curr = curr.next
                 if curr:
                     continue
                 else:
                     prev.next = None
             else:
                 dul = curr.val
                 prev.next = curr
                 curr = curr.next
                 if curr and curr.val != dul:
                     prev = prev.next
         return dmy.next