83. Remove Duplicates from Sorted List

정렬된 연결 리스트에서 중복된 노드를 제거하는 문제입니다. 

문제 설명:

정렬된 연결 리스트가 주어집니다. 이 연결 리스트에서 중복된 노드를 제거하여 중복된 노드가 하나만 남도록 하세요.

예를 들어, 입력으로 주어진 연결 리스트가 다음과 같다고 가정합시다:

1 -> 1 -> 2

이 경우, 중복된 노드인 1이 하나만 남아야 합니다. 따라서 결과 연결 리스트는 다음과 같아야 합니다:

1 -> 2

예시:

Input: 1 -> 1 -> 2
Output: 1 -> 2

Input: 1 -> 1 -> 2 -> 3 -> 3
Output: 1 -> 2 -> 3

노트:

연결 리스트는 정렬되어 있으며, 중복된 노드는 인접해 있을 것입니다.
이 문제를 해결하기 위해 주어진 연결 리스트를 순회하면서 중복된 노드를 제거하고, 중복되지 않은 노드만을 유지하도록 코드를 작성해야 합니다. 이때, 중복된 노드를 제거하는 작업은 이전 노드와 현재 노드의 값을 비교하여 수행됩니다.

 

public ListNode DeleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode current = head;
    
    while (current != null && current.next != null) {
        if (current.val == current.next.val) {
            current.next = current.next.next; // 중복된 노드를 건너뛰기
        } else {
            current = current.next; // 중복되지 않은 경우 다음 노드로 이동
        }
    }
    
    return head;
}

먼저, 주어진 연결 리스트가 null이거나 연결 리스트에 노드가 하나만 있는 경우는 이미 중복된 노드가 없는 상태이므로 그대로 반환합니다.

그런 다음, 연결 리스트를 순회하면서 각 노드와 다음 노드를 비교합니다.

만약 현재 노드의 값과 다음 노드의 값이 같다면 중복된 노드이므로 current.next를 건너뛰어 다음 다음 노드로 이동합니다.

중복된 노드가 아닌 경우, 현재 노드를 다음 노드로 이동하여 다음 노드와 비교합니다.

이런 방식으로 중복된 노드를 제거하면 연결 리스트에서 중복된 노드가 하나만 남게 됩니다.

코드를 실행하면 중복된 노드가 제거된 연결 리스트가 반환됩니다.

 

 

 public ListNode DeleteDuplicates(ListNode head) {
         if (head == null) {
        return head;
    }
        HashSet<int> seen = new HashSet<int>();
        seen.Add(head.val);
        ListNode current= head.next;
        ListNode prev = head;
        while(current != null){
            if(seen.Contains(current.val)){
                prev.next = current.next;
            }
            else{
                seen.Add(current.val);
                prev = current;
            }
            current = current.next;
        }
        return head;
    }

먼저, 주어진 연결 리스트의 head가 null인 경우는 빈 연결 리스트이므로 그대로 반환합니다.

HashSet<int> seen = new HashSet<int>()을 사용하여 중복된 값을 저장하는 해시 집합(HashSet)인 seen을 생성합니다. 이 해시 집합은 중복된 노드의 값을 저장하고 중복을 확인하는 데 사용됩니다.

seen.Add(head.val)를 사용하여 연결 리스트의 첫 번째 노드의 값을 seen 해시 집합에 추가합니다. 이렇게 함으로써 첫 번째 노드의 값을 기준으로 중복 여부를 확인합니다.

ListNode current = head.next를 사용하여 현재 노드 current를 초기화하고, ListNode prev = head를 사용하여 이전 노드 prev도 초기화합니다.

while (current != null) 루프를 사용하여 연결 리스트를 순회합니다. 현재 노드 current가 null이 아닐 때까지 루프가 계속됩니다.

if (seen.Contains(current.val))를 사용하여 seen 해시 집합에 현재 노드의 값이 이미 존재하는지 확인합니다. 즉, 중복된 노드인지 검사합니다.

만약 중복된 노드가 발견되면, 이전 노드 prev의 next를 현재 노드 current.next로 변경하여 중복된 노드를 건너뛰게 됩니다. 이렇게 하면 중복된 노드가 제거됩니다.

중복된 노드가 아닌 경우, 현재 노드의 값을 seen 해시 집합에 추가하고 이전 노드 prev를 현재 노드 current로 업데이트합니다.

current = current.next를 사용하여 현재 노드를 다음 노드로 이동합니다.

루프가 종료되면 중복된 노드가 제거된 연결 리스트를 반환합니다.

이 코드는 중복된 값을 해시 집합을 사용하여 저장하고 중복된 노드를 제거하는 방식으로 동작합니다. 코드의 시간 복잡도는 연결 리스트를 한 번 순회하므로 O(n)입니다.