2.7 Implement a function to check if a linked list is a palindrome.

2.7.cpp

#include<iostream>

using namespace std;

struct Node
{
    int data;
    Node *next;
    
    Node(int data, Node *next) {
        this->data = data;
        this->next = next;
    }
    
    ~Node() {}
};

typedef Node* pNode;

void print(Node * head)
{
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

void clear(Node *head)
{
    if (head != nullptr) {
        while(head->next != nullptr) {
            Node *t = head->next;
            head->next = t->next;
            delete t;
        }
        delete head;
    }
}

pNode mid(pNode slow, pNode fast)
{
    if (fast == nullptr)
        return slow;
    else if (fast->next == nullptr)
        return slow->next;
    
    pNode m = mid(slow->next, fast->next->next);
    
    if (m != nullptr) {
        if (slow->data == m->data)
            return m->next ? m->next : fast;
    }
    
    return nullptr;
}

bool isPalindrome(pNode head)
{
    return mid(head, head) == head;
}

int main(int argc, char *argv[])
{
    pNode a = new Node(1, new Node(2, new Node(3, new Node(3, new Node(2, new Node(1, nullptr))))));
    print(a);
    cout << (isPalindrome(a) ? "True" : "False") << endl;
    clear(a);
    a = new Node(1, new Node(2, new Node(3, new Node(2, new Node(1, nullptr)))));
    print(a);
    cout << (isPalindrome(a) ? "True" : "False") << endl;
    clear(a);
    return 0;
}