Determining if a Linked List is Palindromic

Problem

Given a singly linked list, determine whether or not the list is palindromic.
Example input:
1 -> 2 -> 3 -> 2 -> 1
Example output:
True

Solution

This solution is in C++. Our A.I. can create solutions in multiple languages.

kayakane

#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;
};

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 = new Node();
    head->data = 1;
    head->next = new Node();
    head->next->data = 2;
    head->next->next = new Node();
    head->next->next->data = 3;
    head->next->next->next = new Node();
    head->next->next->next->data = 2;
    head->next->next->next->next = new Node();
    head->next->next->next->next->data = 1;
    cout << isPalindrome(head) << endl;
    return 0;
}