/**
* Definition for singlylinked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null) {
return true;
}
ListNode p1 = head;
ListNode p2 = head;
ListNode p3 = p1.next;
ListNode pre = p1;
//find mid pointer, and reverse head half part
while(p2.next != null && p2.next.next != null) {
p2 = p2.next.next;
pre = p1;
p1 = p3;
p3 = p3.next;
p1.next = pre;
}
//odd number of elements, need left move p1 one step
if(p2.next == null) {
p1 = p1.next;
}
else { //even number of elements, do nothing
}
//compare from mid to head/tail
while(p3 != null) {
if(p1.val != p3.val) {
return false;
}
p1 = p1.next;
p3 = p3.next;
}
return true;
}
}
Easy understand JAVA solution (O(1) space cost)


People, please stop spamming. We understand you guys know each other and are excited about it but please reserve that for personal chats.
Also, I found your variable (p1, p2, p3, etc.) naming a little confusing as an external reader.
I found your approach very similar to what I implemented, so I'll paste it below:public boolean isPalindrome(ListNode head) { // Trivial case if(head == null  head.next == null) { return true;} ListNode start = new ListNode(0); start.next = head; ListNode firstHalfStart = head; ListNode secondHalfStart = head; ListNode fast = head; // Traverse to mid node and Reverse the First half of the LinkedList in the same run while(fast.next != null && fast.next.next != null) { fast = fast.next.next; start.next = secondHalfStart.next; secondHalfStart.next = secondHalfStart.next.next; start.next.next = firstHalfStart; firstHalfStart = start.next; } // Offset for odd number of elements // As the mid node is common to both halves, this should be skipped if(fast.next == null) { firstHalfStart = firstHalfStart.next; } // At the end of the previous loop, SecondHalfStart pointer is still stuck on the end of the first half // Shift it by one to take it to the start of the SecondHalf secondHalfStart = secondHalfStart.next; while(secondHalfStart != null) { if(firstHalfStart.val != secondHalfStart.val) { return false;} secondHalfStart = secondHalfStart.next; firstHalfStart = firstHalfStart.next; } return true; }

An accepted concise version:
public boolean isPalindrome(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } if(fast != null) slow = slow.next; slow = reverse(slow); while(slow != null && head.val == slow.val) { head = head.next; slow = slow.next; } return slow == null; } private ListNode reverse(ListNode head) { ListNode prev = null; while(head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; }