[7. 연결리스트] 7.12 리스트의 피벗 구현하기

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

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

---

https://msugi.tistory.com/47

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

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

---

Q 7.12 리스트의 피벗 구현하기

어떤 정수k를 기준으로 k보다 key가 작은 노드는 왼쪽에, k보다 키가 큰 노드는 오른쪽에 배치하는 과정을 피버팅 이라고 한다. 이때 리스트의 피벗을 구현하라.
ex) 3 2 2 11 7 5 11   => key=7  => 3 2 2 5 7 11 11

---

해당문제의 소스코드와 결과는 https://msugi.tistory.com/47 의 내부 내용으로 작성 했으나 한번 더 소스코드를 작성해보면 다음과 같다. 문제는 단순 연결리스트지만 이중 연결리스트로 구현하였다.

//마지막이 nullptr인 단순구조에서의 피벗
template<class T>
inline void LinkedList<T>::ListPivoting(List<T>* L, int x) // 문제 7.12
{
    Node<T>* DummyHead = new Node<T>();
    Node<T>* LeftList = new Node<T>();
    Node<T>* CenterList = new Node<T>();
    Node<T>* RightList = new Node<T>();
    Node<T>* TempTail = new Node<T>();
    
    DummyHead->NextNode = L->HeadNode;
    DummyHead = DummyHead->NextNode;
    bool bRightTail = true;
 
    while (DummyHead)
    {
        if (DummyHead->data < x)
        {
            LeftList->NextNode = DummyHead;
            DummyHead->PrevNode = LeftList;
            LeftList = LeftList->NextNode;
        }
        else if (DummyHead->data == x)
        {
            CenterList->NextNode = DummyHead;
        }
        else if (DummyHead->data > x)
        {
            RightList->NextNode = DummyHead;
            DummyHead->PrevNode = RightList;
            if (bRightTail)
            {
                TempTail = DummyHead;
                bRightTail = false;
            }
            RightList = RightList->NextNode;
        }
        DummyHead = DummyHead->NextNode;
    }
 
    LeftList->NextNode = CenterList->NextNode;
    CenterList->NextNode->PrevNode = LeftList;
    CenterList->NextNode->NextNode = TempTail;
    TempTail->PrevNode = CenterList->NextNode;
    RightList->NextNode = nullptr;
    L->TailNode = RightList;
    L->HeadNode->PrevNode = nullptr; // 위에서 LeftList를 바로사용하여 초기data값 0 이 계속 남아있는것을 삭제
    
    TempTail = nullptr;
    CenterList = CenterList->PrevNode;
    RightList = RightList->NextNode;
 
    while (LeftList) //동적할당된 LeftList를 지우기위한 작업
    {
        LeftList = LeftList->NextNode;
    }
    delete LeftList;
    delete TempTail;
    delete RightList;
    delete CenterList;
    delete DummyHead;
}

L9는 4 1 3 5 7 8 6 4 2 를 가지고 있는 LinkedList이며 key = 6 일때로 피벗하면 다음과 같다.

//mainL9.AddNode(L9.list, L9.CreateNode(4));
for (int i = 1; i < 9; i += 2)
{
    L9.AddNode(L9.list, L9.CreateNode(i));
}
for (int i = 8; i > 0; i -= 2)
{
    L9.AddNode(L9.list, L9.CreateNode(i));
}
L9.list->TailNode->NextNode = nullptr;
L9.list->HeadNode->PrevNode = nullptr; 
 
L9.ListPivoting(L9.list, 6);
std::cout << "\n7-12) " << std::endl;
L9.PrintAllNode(L9.list); // 7-12

결과