1
class Solution {
2
  public boolean isPalindrome(ListNode head) {
3

4
    ListNode mid = getMiddle(head);
5
    ListNode headSecond = reverse(mid);
6
    ListNode reverseHead = headSecond;
7

8
    while (head != null && headSecond != null) {
9
      if (head.val != headSecond.val) {
10
        break;
11
      }
12
      head = head.next;
13
      headSecond = headSecond.next;
14
    }
15
    reverse(reverseHead);
16

17
    return head == null || headSecond == null;
18
  }
19

20
  public ListNode reverse(ListNode head) {
21
    if (head == null) return head;
22
    ListNode prev = null;
23
    ListNode present = head;
24
    ListNode next = head.next;
25
    while (present != null) {
26
      present.next = prev;
27
      prev = present;
28
      present = next;
29
      if (next != null) next = next.next;
30
    }
31
    return prev;
32
  }
33

34
  public ListNode getMiddle(ListNode head) {
35
    ListNode temp = head;
36
    int count = 0;
37
    while (temp != null) {
38
      temp = temp.next;
39
      count++;
40
    }
41
    int mid = count / 2;
42
    temp = head;
43
    for (int i = 0; i < mid; i++) {
44
      temp = temp.next;
45
    }
46
    return temp;
47
  }
48
}