Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
Input: 1->1->2 Output: 1->2
Example 2:
Input: 1->1->2->3->3 Output: 1->2->3
Description taken from https://leetcode.com/problems/remove-duplicates-from-sorted-list/.
#O(N) Time, O(1) Spaceclass Solution: def deleteDuplicates(self, head: ListNode) -> ListNode: dummy = ListNode(0) dummy.next = head prev, curr = dummy, head while curr and curr.next: next_node = curr.next if curr.val == next_node.val: prev.next = next_node else: prev = curr curr = next_node return dummy.nextThis question has a similar solution to Remove Linked List Elements.
Linked lists are built from next reference pointers. If we want to remove a node, we can remove the reference to it within the list.
We can solve this question by traversing the linked list and if we get to a node that shares a value with the next node, we will set the previous node's next pointer to the next node of the iteration, removing the reference to the current node and removing it from the linked list.
Let's start by initializing a dummy head and setting the dummy head's next pointer to the actual head.
Then, we will set the previous pointer as the dummy head and the current pointer as the actual head.
dummy = ListNode(0) dummy.next = head prev, curr = dummy, head
We will then create a loop to traverse the linked list that will run while the current node hasn't reached a null value.
while curr and curr.next:
During each iteration, we will create a next_node variable to track the next node.
next_node = curr.next
If the current node's value is the same as the next node's, we will set the previous node's next pointer to the next node, removing the current node from the list.
if curr.val == next_node.val: prev.next = next_node
If that's not the case, we will move the previous pointer forward.
else: prev = curr
At the end of each iteration, we will move the current pointer to the next node.
curr = next_node
Once we have traversed the entire list and removed all of the unwanted nodes, we will return the list starting with the head.
return dummy.next