# Java Solution by reversing half of the list. O(n) time. O(1) extra space.

• ``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/

//Uses O(n) time and O(1) space.

class Solution {

while(curr!=null) {
next = curr.next;
curr.next = prev;

prev = curr;
curr = next;
}
// prev is the new head now.
return prev;
}

// 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
slow.next=null;

// Parse and compare both halves' elements one by one.
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.