[7. 연결리스트] 7.10 짝수-홀수 병합 구현하기

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

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

---

https://msugi.tistory.com/47

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

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

---

Q 7.10 짝수-홀수 병합 구현하기

입력받은 연결리스트의 연결 순서를 짝수 노드 다음에 홀수 노드가 등장하도록 배치하시오.
ex) 1,2,3,4,5,6,  => 2,4,6,1,3,5

---

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

//마지막이 nullptr인 단순연결에서 가능
template<class T>
inline void LinkedList<T>::EvenOddMerge(List<T>* L) //문제 7.10
{
    if (!L) { return; }
    Node<int>* temp = L->HeadNode->NextNode;
    Node<int>* EvenDummyHead = nullptr;
    Node<int>* OddDummyHead = nullptr;
 
    if (temp->data % 2 == 0)
    {
        EvenDummyHead = temp;
        OddDummyHead = L->HeadNode;
        EvenDummyHead->PrevNode = nullptr;
    }
    else if (temp->data % 2 == 1)
    {
        EvenDummyHead = L->HeadNode;
        OddDummyHead = temp;
        EvenDummyHead->PrevNode = nullptr;
    }
    else
    {
        return;
    }
    
    while (temp->NextNode != nullptr && EvenDummyHead->NextNode != nullptr)
    {
        EvenDummyHead->NextNode = EvenDummyHead->NextNode->NextNode;
        if (EvenDummyHead->NextNode != nullptr)
        {
            EvenDummyHead->NextNode->PrevNode = EvenDummyHead;
            EvenDummyHead = EvenDummyHead->NextNode;
        }
 
        temp->NextNode = temp->NextNode->NextNode;
        if (temp->NextNode != nullptr)
        {
            temp->NextNode->PrevNode = temp;
            temp = temp->NextNode;
        }
    }
    EvenDummyHead->NextNode = OddDummyHead;
    OddDummyHead->PrevNode = EvenDummyHead;
    L->TailNode = temp;
}

//mainfor (int i = 0; i <= 10; i++)
{
    L7.AddNode(L7.list, L7.CreateNode(i));
}
L7.list->TailNode->NextNode = nullptr;
 
std::cout << "\n7-10) ";
L7.EvenOddMerge(L7.list);
L7.PrintAllNode(L7.list); // 7-10

L7은 0부터 10까지 들어있는 LinkedList

결과