Remove Duplicates from Sorted List

Link : Remove Duplicates from Sorted List

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.

Ex 1:

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

Ex 2:

• Input: head = [1,1,2,3,3]
• Output: [1,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. (오름차순 정렬)

Java code

// import java.util.HashSet;

//Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}


class LC3 {
//    public ListNode deleteDuplicates(ListNode head) {
//        HashSet<Integer> hashSet = new HashSet<>();
//        ListNode prev = null;
//        ListNode now = head;
//        while(now != null){
//            if(hashSet.contains(now.val)){
//                prev.next = now.next;
//            } else {
//                hashSet.add(now.val);
//                prev = now;
//            }
//            now = now.next;
//        }
//        return head;
//    }
public ListNode deleteDuplicates(ListNode head) {
    // sorted! 문제 조건을 잘 읽자
    ListNode prev = null;
    ListNode now = head;
    while(now != null){
        if(prev != null && now.val == prev.val){
            prev.next = now.next;
        } else {
            prev = now;
        }
        now = now.next;
    }
    return head;
}
}

풀이

• 원래 풀었던 코드는 주석 처리가 되었는데, 컬렉션을 쓰는 순간 효율이 급감하는 것을 처음 알았다.
• 따라서 어떻게하면 복잡도를 줄일 수 있으면서, 이전에 나왔던 노드값을 저장?할 수 있을까를 고민했다.
• 그러던 찰나, 문제를 보니 sorted라고 강조가 되어있었다... 이말인 즉슨 다음 값과의 비교만 하고 굳이 값을 저장할 필요가 없다는 것이다.. (문제 조건을 제발 잘 읽자! ㅠ)
• 따라서 현재 노드가 있을 때 while문을 돌면서 이전 노드가 null 값이 아니고, 현재 노드의 val 값과 이전 노드의 val 값을 비교하여 다르다면 연결을 이전 노드 -> 다음 노드로 해준다.
• 만약 val 값이 다르다면 계속하여 진행한다.

교훈

• 문제를 잘 읽자. (조건 포함!)