Given a singly linked list, determine if it is a palindrome.

Example 1:

``````Input: 1->2
Output: false``````

Example 2:

``````Input: 1->2->2->1
Output: true``````

Follow up: Could you do it in O(n) time and O(1) space?

Analysis

In the beginning, set two pointers`fast`and`slow`starting at the head.

``````1 -> 1 -> 2 -> 1 -> null
sf``````

(1) Move:`fast`pointer goes to the end, and`slow`goes to the middle.

``````1 -> 1 -> 2 -> 1 -> null
s          f``````

(2) Reverse: the right half is reversed, and`slow`pointer becomes the 2nd head.

``````1 -> 1    null <- 2 <- 1
h                      s``````

(3) Compare: run the two pointers`head`and`slow`together and compare.

``````1 -> 1    null <- 2 <- 1
h            s``````

Solution

Find Mid Point + Reverse + Compare --- O(n) time, O(1) space

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
ListNode fast, slow;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null) {
slow = slow.next;
}
slow = reverse(slow);

while (fast != null && slow != null) {
if (fast.val != slow.val) {
return false;
}
fast = fast.next;
slow = slow.next;
}
return true;
}

ListNode prev = null;

while (curr != null) {
ListNode tmpNext = curr.next;
curr.next = prev;
prev = curr;
curr = tmpNext;
}
return prev;
}
}``````

Don't need to make the right half smaller: https://leetcode.com/problems/palindrome-linked-list/discuss/64501/Java-easy-to-understand/66206

``````public boolean isPalindrome(ListNode head) {
return true;
}
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
slow = reverse(slow);
while (head != null && slow != null) {