using System;

using System.Collections.Generic;

​

 public class ListNode {

      public int val;

      public ListNode next;

      public ListNode(int x) {this.val = x; this.next = null;}

  }

​

public class Program

{

    public static void Main()

    {

        var list = new ListNode(2);

        var last = list;

        last.next = new ListNode(2);

        last = last.next;

        last.next = new ListNode(1);

        last = last.next;

​

        Console.WriteLine(IsPalindrome(list));

    }

    public static int IsPalindrome(ListNode list)

    {

        if (list is null)

        {

            throw new Exception("List is empty");

        }

        var stack = new Stack<int>();

        var first = list;

        while (list is not null)

        {

            stack.Push(list.val);

            list = list.next;

        }

        list = first;

        while (stack.Count != 0)

        {

            var stackVal = stack.Pop();

            var listVal = list.val;

            list = list.next;

            if (stackVal != listVal)

            {

                return 0;

            }

        }

        return 1;

    }

}