[7. 연결리스트] 7.8 정렬된 리스트에서 중복된 원소 삭제하기

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

https://msugi.tistory.com/47

[7. 연결리스트] 7.0 연결리스트 기초 작업

연결리스트 문제를 풀기전 LinkedList를 위와 같이 직접 구현했다. 위 LikedList를 이용하여 문제를 풀 예정이다.

---

Q 7.8 정렬된 리스트에서 중복된 원소 삭제하기

정렬된 정수 리스트에서 중복되는 부분을 제거하면 된다.
ex) 2 2 3 5 7 1 1   ->  2 3 5 7 1

---

해당문제의 소스코드와 결과는 https://msugi.tistory.com/47 의 내부 내용으로 작성 했으나 한번 더 소스코드를 작성해보면 다음과 같다.

//정렬이 되어있을때 적용가능하다.
template<class T>
inline void LinkedList<T>::RemoveDuplicates(List<T>* L) // 문제 7.8 해당 함수로 대체
{
    Node<T>* iter = L->HeadNode;
    int count = L->Count;
    while(iter && --count > 0)
    {
        auto NextDistinct = iter->NextNode;
        while (NextDistinct && NextDistinct->data == iter->data)
        {
            NextDistinct = NextDistinct->NextNode;
            delete iter->NextNode;
            L->Count--;
        }
        iter->NextNode = NextDistinct;
        NextDistinct->PrevNode = iter;
        iter = iter->NextNode;
        L->TailNode = iter;
    }
}

 

// main LinkedList<int> L6;
for (int i = 1; i <= 5; i++)
{
    L6.AddNode(L6.list, L6.CreateNode(i));
    L6.AddNode(L6.list, L6.CreateNode(i));
}
std::cout << "\n7-8) ";
L6.PrintAllNode(L6.list);
 
L6.RemoveDuplicates(L6.list);
L6.PrintAllNode(L6.list); // 7-8

결과