234 Palindrome Linked List *** idea!! find the median and then reverse

solve the question in O(n) time and o(1) space

if not have the restriction, then you could store all the numbers in array and then check

or you could use a stack

but if O(1) space, you could only choose find the median, and reverse the last half and see if it is a palindrome

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode median = findMedian(head);
        ListNode medNext = median.next;
        median.next = null;
        ListNode rightHead = reverseList(medNext);
        ListNode leftHead = head;
        while (leftHead != null && rightHead != null) {
            if (leftHead.val == rightHead.val) {
                leftHead = leftHead.next;
                rightHead = rightHead.next;
            }else {
                return false;
            } 
        }
        return true; 
    }
    public ListNode findMedian (ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverseList (ListNode node) {
        if (node.next == null) {
            return node;
        }
        ListNode curt = node;
        ListNode prev = null;
        while (curt != null) {
          ListNode temp = curt.next;
            curt.next = prev;
            prev = curt;
            curt = temp;
        }
        return prev;
    }
}