```
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
//Uses O(n) time and O(1) space.
class Solution {
private ListNode reverse(ListNode head) {
if (head == null || head.next == null) return head;
ListNode curr=head, prev=null, next=head;
while(curr!=null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// prev is the new head now.
return prev;
}
public boolean isPalindrome(ListNode head) {
ListNode slow = head, fast = head;
if (head==null || head.next==null) return true;
// Find the mid point of linked list.
while(fast!=null && fast.next!=null) {
fast = fast.next;
if (fast==null || fast.next==null) {
break;
}
fast = fast.next;
slow = slow.next;
} // slow is the mid point of linked list.
// Temporarily split list into two halves. Reverse the second half
ListNode head2 = slow.next;
slow.next=null;
head2 = reverse(head2);
// Parse and compare both halves' elements one by one.
ListNode ptr1 = head, ptr2 = head2;
while (ptr1 != null && ptr2 != null) {
if (ptr1.val != ptr2.val) {
return false;
}
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
// At this point. list is definitely a palindrome.
// Even list: Both halves are empty and same val.
// Odd list: Both halves have same values but one half has one element remaining. Since single remaining element is also palindrome, it is true.
// Revert the second half of list, connect both halves and return true.
head2 = reverse(head2);
slow.next = head2;
return true;
}
}
```