Delete duplicate-value nodes from a sorted linked list

주어진 정렬된 연결 리스트(Linked List)에서 중복된 값을 가지는 노드들을 제거하는 알고리즘 문제입니다. 이 문제의 목표는 정렬된 연결 리스트에서 중복된 값을 가지는 노드를 제거한 후, 중복이 없는 연결 리스트를 반환하는 것입니다.

연결 리스트는 데이터 요소(Node)로 이루어진 데이터 구조로, 각 노드는 데이터와 다음 노드를 가리키는 링크(또는 포인터)로 구성됩니다. 연결 리스트의 끝을 나타내는 노드는 다음 노드를 가리키는 링크가 없는 특별한 노드일 수 있습니다.

문제 설명:
문제의 입력으로는 정렬된 연결 리스트 llist가 주어집니다. 이 정렬된 연결 리스트에서 중복된 값을 가지는 노드를 제거한 후, 중복이 없는 연결 리스트를 반환해야 합니다.

알고리즘 절차:

정렬된 연결 리스트를 순회하면서 각 노드의 데이터 값을 비교합니다.
현재 노드와 다음 노드의 데이터 값을 비교하여 중복된 경우 다음 노드를 건너뛰고 다음 다음 노드로 이동합니다.
중복이 없는 경우, 현재 노드를 다음 노드로 이동합니다.
위의 과정을 연결 리스트의 끝까지 반복합니다.
중복이 없는 연결 리스트를 반환합니다.

 

SinglyLinkedListNode* removeDuplicates(SinglyLinkedListNode* llist) {
    SinglyLinkedListNode* current = llist; // 현재 노드를 가리키는 포인터

    // 연결 리스트를 순회하면서 중복된 노드 제거
    while (current) {
        SinglyLinkedListNode* next = current->next; // 다음 노드를 가리키는 포인터

        // 다음 노드가 존재하고, 현재 노드의 데이터와 다음 노드의 데이터가 같은 경우
        if (next && current->data == next->data) {
            current->next = next->next; // 현재 노드를 다음 다음 노드로 연결하여 중복된 노드 삭제
            // 중복된 노드인 next는 메모리에서 해제되지 않았으므로 메모리 누수의 가능성이 있음
        }
        else {
            current = current->next; // 중복이 없는 경우 다음 노드로 이동
        }
    }

    return llist; // 중복이 없는 연결 리스트 반환
}

 

1. 연결 리스트를 순회하면서 현재 노드와 다음 노드의 데이터 값을 비교합니다.
2. 만약 다음 노드가 존재하고, 현재 노드의 데이터와 다음 노드의 데이터가 같다면, 현재 노드를 다음 다음 노드로 연결하여 중복된 노드를 삭제합니다.
3. 중복이 없는 경우, 현재 노드를 다음 노드로 이동하여 다음 노드를 검사합니다.
4. 이러한 과정을 연결 리스트의 끝까지 반복하면 중복이 없는 연결 리스트가 생성됩니다.