[7. 연결리스트] 7.11 단순 연결리스트가 회문인지 확인하기

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

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

---

https://msugi.tistory.com/47

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

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

---

Q 7.11 단순 연결리스트가 회문인지 확인하기

각 끝의 앞뒤가 nullptr을 가리키는 연결리스트가 회문인지 판단하라.

---

간단하게 리스트를 앞뒤로 읽어서 비교하도록 했다.
미리 만들어둔 HeadNode와 TailNode를 이용하여 앞뒤로 읽어 값이 맞는지 비교한다
해당 내용의 소스코드와 결과는 다음과 같다.

// 7.11 단순 연결리스트가 회문인지 확인하기 #include "LinkedList.h"
 
bool IsLinkedListAPalindrome(List<int>* L)
{
    Node<int>* Head = L->HeadNode;
    Node<int>* Tail = L->TailNode;
    int count = 0;
    L->Count % 2 == 0 ? count = (L->Count / 2) - 1 : count = L->Count / 2;
    for (int i = 0; i <= count; i++)
    {
        if (Head->data != Tail->data)
        {
            return false;
        }
        Head = Head->NextNode;
        Tail = Tail->PrevNode;
    }
    return true;
}

L7은 문제 7.10까지 사용된 L7을 그대로 사용하여 확인했다.

//mainfor (int i =0; i <= 4; i++)
{
    L8.AddNode(L8.list, L8.CreateNode(i));
}
for (int i = 4; i >= 0; i--)
{
    L8.AddNode(L8.list, L8.CreateNode(i));
}
 
std::cout << "\n7-11) "<<std::endl;
std::cout << std::boolalpha<< IsLinkedListAPalindrome(L7.list) << std::endl; //7-11
std::cout << std::boolalpha<< IsLinkedListAPalindrome(L8.list) << std::endl; //7-11

결과