IP#5 : LinkedList Removing Duplicates II

 Removing Duplicates II

by Ashur Baroutta

       In our last submissions, we worked on removing duplicates, this week we look at the more complicated problem of the same type. Our problem statement is "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."
    

So not only do we have to remove duplicates, but we cannot return values that are not distinct, for example, if our list originally contained three 1's, we need to delete all the 1's in our list as even if we delete all but one of them, the number 1 itself is not a distinct value. 
    This took me about 3 days to think through and complete, the following is our code submission. 

We start by first creating a new ListNode called newlist. We set its .next reference pointing to head (the ListNode passed initially). Then we make a ListNode current pointing to newlist. 

We will also be utilizing nested loops, our first loop breaks when either current, its next reference, or current.next's next reference are equal to null. Inside of that loop we have our if condition checking if current.next's value is equal to the next nodes value as if it is, we initialize a  temp node and set it pointing to current.next. 

That is done in order for us to now start our nested loop to iterate until either temp is null or current.next's value is not equal to temp's value. As it's iterating it will continue to change temp equal to its next reference as we cannot have duplicates and must only return distinct values in our newlist. 

Once we've broken out of the nested loop, remember we are still inside our first loop now and our if condition, we change current.next pointing to temp as temp is a distinct value. 

Else (when our if condition doesn't apply) we just keep changing current to equal its next reference and loop to check our conditions again. Solving our problem by iteratively removing duplicates and non distinct numbers!

While I am happy I was able to land on a solution, regrettably it was not without a lot of help. This was probably the most frustrated I've been trying to solve a problem though I look forward to continue attacking my understanding of data structures and more specifically the relationship between nodes within a linked list. 

As we can see, the rankings in terms of speed/memory are not the best they can be. I have a lot of work left to understand how to better optimize this code.