Problem Description
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
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]
Constraints:
- The number of nodes in the list is in the range
[0, 300]. -100 <= Node.val <= 100- The list is guaranteed to be sorted in ascending order.
The description was taken from https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/.
Problem Solution
#O(N) Time, O(1) Space
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr and curr.next:
if curr.val == curr.next.val:
while curr.next and curr.next.val == curr.val:
curr = curr.next
prev.next = curr.next
else:
prev = prev.next
curr = curr.next
return dummy.nextProblem Explanation
The difference between this problem and the first Remove Duplicates from Sorted List is we will need to remove the entire group of duplicates.
To do that, since the list is already sorted, we will just iterate through the list and once we find a node that is the same as the current, we will continue iterating until we find the next one. In which case, we will set the previous unique node's next pointer to the next different node.
We'll start by setting a dummy node before the head in case we need to remove the head later, it will be easy knowing where the list started.
dummy = ListNode(0)
dummy.next = head
Then, we will create a previous and a current node pointer to the dummy head and the head.
prev, curr = dummy, head
Next, we will begin our traversal.
The traversal will continue until the current node's next pointer is null since we will be setting pointers to the next node in our processing.
while curr and curr.next:
In our traversal, if we stumble upon a node that is the same as the current, we will continue iterating until we find the first different node.
if curr.val == curr.next.val:
while curr.next and curr.next.val == curr.val:
curr = curr.next
Once we find that first different node, we will set the previous node's next pointer to the current node's next node.
This will snip the entire group of duplicates.
dummy->1->2->2->3->4->None
dummy->1->3->4->None
prev.next = curr.next
If the current node isn't the same as the next node, then this node is unique so we will set the previous node pointer, which is what we are using to track unique nodes, to this node.
else:
prev = prev.next
Once we have finished setting pointers, we will continue to the next node.
curr = curr.next
Once we have finished traversing the linked list, we will return the head, which will be at the dummy head's next pointer.
return dummy.next