Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Input: 1->2->3->3->4->4->5 Output: 1->2->5
Input: 1->1->1->2->3 Output: 2->3
While iterating through the linked list, keep track of the previous distinct node and the first distinct node (aka new head). Don’t forget to handle the last element and
next of the previous distinct node.
# 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 new_head = None prev = None curr = head curr_val = curr.val counter = 1 while curr.next is not None: if curr.next.val == curr_val: counter += 1 else: if counter == 1: if new_head is None: new_head = curr if prev is not None: prev.next = curr prev = curr curr_val = curr.next.val counter = 1 curr = curr.next # Handle the last element if prev is not None: if counter == 1: prev.next = curr else: prev.next = None if new_head is None and counter == 1: new_head = curr return new_head