using System;

using System.Collections.Generic;

public class Program

{

    public class LinkedListNode<T>{

        public T Value {get;set;}

        public LinkedListNode<T> Next;

        public LinkedListNode(T val, LinkedListNode<T> next=null){

            this.Value = val;

            this.Next = next;   

        }

    }

    public static LinkedListNode<T> CreateLinkedList<T>(List<T> values){

        if (values==null) return null;

        LinkedListNode<T> lastNodeCreated = null;

        for (var i=values.Count-1; i>=0; i--){

            var node = new LinkedListNode<T>(values[i],lastNodeCreated);

            lastNodeCreated = node;

        }

        return lastNodeCreated;

    }

    public static void PrintLinkedList<T>(LinkedListNode<T> node){

        if (node==null) return;

        while (node!=null){

            Console.Write(node.Value + " ");

            node=node.Next;

        }

        Console.WriteLine();

    }

    public static bool IsPalindrome<T>(LinkedListNode<T> node){

        if (node==null) return true;

        var stack = new Stack<T>();

        var head = node;

        while (node!=null){

            stack.Push(node.Value);

            node=node.Next;

        }

        node = head;

        while (stack.Count!=0){

            var element = stack.Pop();

            if (!node.Value.Equals(element)) return false;

            node=node.Next;

        }

        return true;

    }

    public static void Main()

    {

        var root1 = CreateLinkedList<char>(new List<char>{'a','b','c','c','b','a'});

        var root2 = CreateLinkedList<char>(new List<char>{'a','b','c','c','d','a'});

        var root3 = CreateLinkedList<char>(new List<char>{'a','b','c','b','a'});

        Console.WriteLine("Hello World");

        Console.WriteLine(IsPalindrome(root1));

        Console.WriteLine(IsPalindrome(root2));

        Console.WriteLine(IsPalindrome(root3));

    }

}