LeetCode - 정렬된 목록 II에서 중복 제거

문제 설명

정렬된 연결 목록의 헤드가 주어지면 원래 목록에서 고유한 번호만 남기고 중복 번호가 있는 모든 노드를 삭제합니다. 정렬된 연결 리스트도 반환합니다.

문제 진술 출처: https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii

예 1:

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

예 2:

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

제약:

- 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.

설명

해시 맵 사용

간단한 해시 맵을 사용하여 문제를 해결할 수 있습니다. 노드 값을 해시 맵 키로 저장합니다. 각 키의 값은 키가 목록에 나타나는 횟수입니다.

그런 다음 이 해시 맵을 반복하고 한 번만 나타나는 키에 대한 새 목록을 만듭니다.

이 논리의 C++ 스니펫은 다음과 같습니다.

ListNode* removeDuplicates(ListNode* head) {
    map<int, int> map;

    map<int, int> map;

    while(head != NULL) {
        map[head->val]++;
        head = head->next;
    }

    ListNode* prev = new ListNode(0);

    for(auto it: map) {
        if(it.second == 1) {
            ListNode* cur = new ListNode(it.first);
            prev->next = cur;
            prev = cur;
        }
    }
}

함수의 시간 복잡도는 O(N)이고 공간 복잡도는 O(N)입니다.

센티넬 사용

예제 1은 두 개의 포인터를 사용하여 해결할 수 있습니다. 예제 2에서는 상황이 까다로워집니다. 연결 목록을 다룰 때 이러한 경우를 많이 접하게 됩니다. 이러한 종류의 문제를 해결하기 위해 Sentinel Node을 사용합니다. 이러한 노드는 유사 헤드 또는 테일로 사용되어 다음과 같은 엣지 케이스를 처리합니다.
예 2.

이 문제를 해결하기 위해 센티넬 헤드를 사용하여 목록 헤드가 삭제되는 상황이 발생하지 않도록 합니다.

입력 목록이 정렬되고 노드 값을 다음 노드와 비교해야 합니다. 우리는 중복 하위 목록 이전의 마지막 노드를 가리키는 선행 포인터를 사용합니다. 중복 하위 목록이 끝나면 중복되지 않은 노드 옆에 있는 선행 노드를 가리킵니다.

알고리즘을 확인해 봅시다:

- set sentinel = ListNode(0)
  point sentinel->next = head
  set predecessor = sentinel

- loop while head != NULL
    // if the sub-list is duplicate
  - if head->next != NULL && head->val == head->next->val

    loop while head->next != NULL && head->val == head->next->val
      - move head = head->next

    // point predecessor's next to the non-duplicate node
    - set predecessor->next = head->next

  - else
    - set predecessor = predecessor->next
  - end if

  - set head = head->next
- end while

// return the new head.
- return sentinel-next

이 함수의 시간 복잡도는 O(N)이고 공간 복잡도는 O(1)입니다.

C++, Golang 및 Javascript에서 솔루션을 확인합시다.

C++ 솔루션

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* sentinel = new ListNode(0);
        sentinel->next = head;
        ListNode* predecessor = sentinel;

        while(head != NULL) {
            if(head->next != NULL && head->val == head->next->val) {
                while(head->next != NULL && head->val == head->next->val) {
                    head = head->next;
                }

                predecessor->next = head->next;
            } else {
                predecessor = predecessor->next;
            }

            head = head->next;
        }

        return sentinel->next;
    }
};

골랑 솔루션

func deleteDuplicates(head *ListNode) *ListNode {
    sentinel := &ListNode{
        Val: 0,
        Next: head,
    }

    predecessor := sentinel

    for head != nil {
        if head.Next != nil && head.Val == head.Next.Val {
            for head.Next != nil && head.Val == head.Next.Val {
                head = head.Next
            }

            predecessor.Next = head.Next
        } else {
            predecessor = predecessor.Next
        }

        head = head.Next
    }

    return sentinel.Next
}

자바스크립트 솔루션

var deleteDuplicates = function(head) {
    let sentinel = new ListNode(0, head);
    let predecessor = sentinel;

    while(head != null) {
        if(head.next != null && head.val == head.next.val) {
            while(head.next != null && head.val == head.next.val) {
                head = head.next;
            }

            predecessor.next = head.next;
        } else {
            predecessor = predecessor.next;
        }

        head = head.next;
    }

    return sentinel.next;
};

솔루션이 어떻게 작동하는지 알아보기 위해 알고리즘을 시험 실행해 보겠습니다.

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

Step 1: ListNode* sentinel = new ListNode(0)

        sentinel->next = head
        sentinel = [0, 1, 1, 1, 2, 3]

        ListNode* predecessor = sentinel
        predecessor = [1, 1, 1, 2, 3]

Step 2: loop while head != NULL
        1 != NULL
        true

        if head->next != NULL && head->val == head->next->val
           1 != NULL && 1 == 1
           true

           loop while head->next != NULL && head->val == head->next->val
                head = head->next

            head = [1, 2, 3]

            predecessor->next = head->next
            predecessor = [2, 3]

        head = head->next
        head = [2, 3]
        sentinel = [0, 2, 3]

Step 3: loop while head != NULL
        2 != NULL
        true

        if head->next != NULL && head->val == head->next->val
           2 != NULL && 2 == 3
           false

        else
           predecessor = predecessor->next
           predecessor = [3]

        head = head->next
        head = [3]
        sentinel = [0, 2, 3]

Step 4: loop while head != NULL
        3 != NULL
        true

        if head->next != NULL && head->val == head->next->val
           NULL != NULL
           false

        else
           predecessor = predecessor->next
           predecessor = NULL

        head = head->next
        head = NULL
        sentinel = [0, 2, 3]

Step 5: loop while head != NULL
        NULL != NULL
        false

Step 6: return sentinel->next
        sentinel = [0, 2, 3]
        sentinel->next = [2, 3]

We return the answer as [2, 3].