# Easy understand JAVA solution (O(1) space cost)

• ``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
return true;
}
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

}
while(p3 != null) {
if(p1.val != p3.val) {
return false;
}
p1 = p1.next;
p3 = p3.next;
}
return true;

}
}``````

• So you use p2 to locate the middle point as p2 moves at double speed of p1's. Cool!

• Reverse half a list can answer the follow up question. But it changes input, which is a bad solution in a practical project. I think we need to point it out during the interview.

• Yes, I agree with you. Actually the code should reverse the list back when it doing the comparation. I'm too lazy to write it down. Sorry for this.

• This post is deleted!

• This post is deleted!

• This post is deleted!

• This post is deleted!

• This post is deleted!

• This post is deleted!

• This post is deleted!

• hahahhaahaha

• This post is deleted!

• 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

ListNode start = new ListNode(0);

// 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;
}``````

• This post is deleted!

• This post is deleted!

• Can we really claim that no list is a palindrome? head == false no?

• This post is deleted!

• An accepted concise version:

``````public boolean isPalindrome(ListNode 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) {
slow = slow.next;
}
return slow == null;
}