```
public class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
ListNode oneStep = head;
ListNode pre = null;
ListNode twoStep = head;
while(twoStep != null && twoStep.next != null) {
pre = oneStep; // Used to when there are even number of nodes.
oneStep = oneStep.next;
twoStep = twoStep.next.next;
}
// If twoStep is null, it means there are even number of nodes. We need to break down the original list
// and then do the reverse
// Even number of nodes, final state as follows.
// oneStep twoStep
// | |
// 1 -> 2 -> 2 -> 1 -> null
// If twoStep.next is null, the list is already broken by reverse() method. No need to break up the list.
// Odd number of nodes, final state as follows.
// oneStep twoStep
// | |
// 1 -> 2 -> 1 -> null
if(twoStep == null) pre.next = null;
// A linked list is palindrome iff the reverse of half of it starting at half point equals another half.
return equals(reverse(oneStep), head);
}
protected boolean equals(ListNode head1, ListNode head2) {
while(head1 != null && head2 != null) {
if(head1.val != head2.val) return false;
head1 = head1.next;
head2 = head2.next;
}
return head1 == null && head2 == null;
}
protected ListNode reverse(ListNode head) {
ListNode node = head;
ListNode newHead = null;
while(node != null) {
ListNode next = node.next;
node.next = newHead;
newHead = node;
node = next;
}
return newHead;
}
}
```