Given the head of a singly linked list, return true if it is a palindrome.
Example 1:
Input: head = [1,2,2,1]
Output: true
Example 2:
Input: head = [1,2]
Output: false
Constraints:
- The number of nodes in the list is in the range [1, 105].
- 0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
// odd nodes: let right half smaller
if (fast != null) {
slow = slow.next;
}
slow = reverse(slow);
fast = head;
while(slow!=null){
if(slow.val!=fast.val){
return false;
}
slow = slow.next;
fast = fast.next;
}
return true;
}
private ListNode reverse(ListNode head){
ListNode pre = null;
ListNode now = head;
while(now!=null){
ListNode next = now.next;
now.next = pre;
pre = now;
now = next;
}
return pre;
}
}