headof 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.
Input: head = [1,2,3,3,4,4,5] Output: [1,2,5]
Input: head = [1,1,1,2,3] Output: [2,3]
- The number of nodes in the list is in the range
-100 <= Node.val <= 100The list is guaranteed to be sorted in ascending order.
import pytest from typing import List from .util import ListNode, toListNode, toList from .Day5 import Solution s = Solution() @pytest.mark.parametrize( "input,expected", [ ([1, 2, 3, 3, 4, 4, 5], [1, 2, 5]), ([1, 2, 3, 3, 3, 4, 4, 5], [1, 2, 5]), ([1, 1, 1, 2, 3], [2, 3]), ([2, 3, 4], [2, 3, 4]), ([1, 1], ), (, ), (, ), ([1, 1, 2, 2], ), ], ) def test_remove_duplicates(input, expected): assert toList(s.deleteDuplicates(toListNode(input))) == expected
class Solution: def deleteDuplicates(self, head: ListNode) -> ListNode: holder = ListNode(0, head) dummy_head = holder next_node = head while next_node: if next_node.next is not None and next_node.next.val == next_node.val: while ( next_node.next is not None and next_node.val == next_node.next.val ): next_node = next_node.next dummy_head.next = next_node.next else: dummy_head = dummy_head.next next_node = next_node.next return holder.next
This was another one I thought would be super easy but I got confused a bunch of times trying to figure out the pointers. I even messed up my first attempt because I didn't read the question correctly and thought I just had to remove duplicates without removing all instances of a number that had a match.
I did think initially I would need to keep pointers for the current head and the next list item. I assumed all I would have to do is increment the
next pointer while there was a match. As soon as we didn't have a match, bump the
next. Of course, we would then need another pointer for
head.next to carry on. I ended up with a bunch of if statements and a mess of code.
It took me a while to realise the easiest thing to do is create a
holder pointer that would easily allow me to increment
head (when there are duplicates at the beginning) and then we can set up a dummy head pointer as well as a
So then we check for duplicates, increment the
next_node pointer for all those duplicates. Then we push the
dummy_head pointer past the duplicates which we can safely do because we kept the original head in the
If we don't see a duplicate we just increment the
dummy_head pointer to the next node in
I feel like if I got this in an interview yesterday I would have been in trouble even though the solution seems so obvious now.