[LeetCode] #83 Remove Duplicates from Sorted List (repeat : 0)

중복값이 나오면 포인터를 리스트에서 빼는 문제이다. 요소를 Set 자료구조에 넣은 후,Set자료구조에 포함되면 이전포인터가 현재포인터를 건너띄고 다음포인터를 향하도록 하였다. 자바인데 컴파일러를 C로 했더니 계속 오류가 낫다 -- 

 

 

# Description

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

 

Example 1:

Input: head = [1,1,2]
Output: [1,2]

Example 2:

Input: head = [1,1,2,3,3]
Output: [1,2,3]

 

 

#Solution 

 

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        
        HashSet<Integer> values = new HashSet<>();
        ListNode prev = null;
        ListNode current = head;
        
        while(current != null){
            if(values.contains(current.val)){
                prev.next = current.next;  // set prev.next to skip the current node
            }else{
                values.add(current.val);
                prev = current; // set the prev node to point the prev node
            }
            current = current.next; // move current node to the next node
        }        
        
        return head;
    }
}

I kept forgot the fact that this data strucutre is LinkedList. since prev is also become part of LinkedList. If i move next node of previous node to skip the current node. the whole LinkedList itself skips the current node !

 

In terms of space complexity, this algorithm uses only three constant variables (values,prev,current) . therefore space complexity is O(1) constant space time. On the other hand, In terms of time complexiy, it is O(n) leaner running time ,n represents the number of nodes in the linkedList