Problem

Given a singly linked list, determine if it is a palindrome.
Example input:
1->2->2->1
Example output:
true

Solution

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* newNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->next = NULL;
    return node;
}

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

bool isPalindrome(Node* head) {
    Node* slow = head;
    Node* fast = head;
    stack<int> s;
    while (fast != NULL && fast->next != NULL) {
        s.push(slow->data);
        slow = slow->next;
        fast = fast->next->next;
    }
    if (fast != NULL) {
        slow = slow->next;
    }
    while (slow != NULL) {
        int top = s.top();
        s.pop();
        if (top != slow->data) {
            return false;
        }
        slow = slow->next;
    }
    return true;
}

int main() {
    Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(2);
    head->next->next->next->next = newNode(1);
    cout << isPalindrome(head) << endl;
    return 0;
}