/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

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

 * }

 */

public class Solution {

    public boolean isPalindrome(ListNode head) {

        ListNode end = head;

        ListNode mid = head;

        while(end != null && end.next != null){

        	end = end.next.next;

        	mid = mid.next;

        }

        if(end != null) //in case of odd list

        	mid = mid.next;

        mid = reverseList(mid);

        while(mid != null){

        	if(mid.val != head.val)

        		return false;

        	mid = mid.next;

        	head = head.next;

        }

        return true;

    }

    public ListNode reverseList(ListNode head){

    	ListNode pre = null, next = null;

    	while(head != null){

    		next = head.next;

    		head.next = pre;

    		pre = head;

    		head = next;

    	}

    	return pre;

    }

}