using System;

public class Program

{

    public static void Main()

    {

        IsPalindrome(new ListNode(5));

    }

    public static bool IsPalindrome(ListNode head) {

        if(head == null || head.next == null)

            return true;

        ListNode fast = head;

        ListNode slow = head;

        while(fast != null && fast.next != null)

        {

            slow  = slow.next;

            fast = fast.next.next;

        }

        if(fast != null)

            slow = slow.next;

        fast = head;

        slow = Reverse(slow);

        while(slow != null)

        {

            if(slow.val != fast.val)

                return false;

            slow = slow.next;

            fast = fast.next;

        }

        return true;

    }

    private static ListNode Reverse(ListNode head)

    {

        ListNode prev = null;

        while(head != null)

        {

            ListNode next = head.next;

            head.next = prev;

            prev = head;

            head = next;

        }

        return prev;

    }

}

​

public class ListNode {

      public int val;

      public ListNode next;

      public ListNode(int x) { val = x; }

 }