Linked List(Check if Linked List is Palindrome)

Linked List is a data structure comprising a sequence of nodes, each containing a reference to the subsequent node in the sequence. Linked lists are vital for dynamic memory allocation and offer primary operations such as insertion, deletion, and traversal. They come in handy when working with variable data sizes, enabling the efficient management of data storage and retrieval.

Representation of Singly-linked list


EX)Check if Linked List is Palindrome

#include <iostream>
#include <stack>

class ListNode {
public:
    int val;
    ListNode* next;

    ListNode(int value) : val(value), next(nullptr) {}
};

bool isPalindrome(ListNode* head) {
    std::stack<int> s;
    ListNode* current = head;

    while (current != nullptr) {
        s.push(current->val);
        current = current->next;
    }

    current = head;
    while (!s.empty()) {
        int top = s.top();
        s.pop();

        if (current->val != top) {
            return false;
        }

        current = current->next;
    }

    return true;
}

int main() {
    // 예제 연결 리스트 생성
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(1);

    bool result = isPalindrome(head);

    if (result) {
        std::cout << "Linked list is a palindrome." << std::endl;
    } else {
        std::cout << "Linked list is not a palindrome." << std::endl;
    }

    // 연결 리스트 메모리 해제
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}