// Definition for singly-linked list:
// class ListNode<T> {
//   ListNode(T x) {
//     value = x;
//   }
//   T value;
//   ListNode<T> next;
// }
//
//

boolean isListPalindrome(ListNode<Integer> l) {

    if(l == null)
        return true;

    Integer length = getListLength(l);
    System.out.println(length);

    int firstInSecondHalfIndex = length%2 == 0 ? length/2 : (length/2) + 1;

    ListNode<Integer> mid = l;
    for(int i=0;i<=firstInSecondHalfIndex;i++){
        if(i==0)
            mid = l;
        else
            mid = mid.next;
    }

    ListNode<Integer> newFirstInSecondHalf = reverse(mid);


    ListNode<Integer> a = l;
    ListNode<Integer> b = newFirstInSecondHalf;
    for(int i=0;i<length/2;i++){
        if(a.value - b.value !=0){
            return false;
        }
        a = a.next;
        b = b.next;
    }

    return true;
}

Integer getListLength(ListNode<Integer> node){

    if(node == null)
        return 0;

    int count = 1;
    while(node.next != null){
        count++;
        node = node.next;
    }
    return count;
}


ListNode<Integer> reverse(ListNode<Integer> head){
    ListNode<Integer> current = head;
    ListNode<Integer> prev = null;
    ListNode<Integer> next;

    while(current != null){
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    return prev;
}