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;
}
}

に答える

元で解読したコードは注釈処理され,コレクションを書く瞬間に効率が急激に低下することが初めて発見された.

以前のノード値をどのように格納し、複雑さを低減しますか?できるかどうか分からない.

の一瞬にして、問題はソートとして強調された...つまり、次の値と比較するだけで、値を格納する必要はありません.(質問条件をよく読んでください!ㅠ)

したがって、現在のノードが存在する場合、ゲートを迂回したときに前のノードが空ではなく、現在のノードのval値が前のノードのval値と比較して異なる場合、接続は이전 노드 -> 다음 노드に設定される.

val値が異なる場合は、続行します.

教訓

題をよく読みなさい.(条件も含めて!)