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?
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
//根据快慢指针求中点
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if(fast != null)
slow = slow.next;
//slow是中点，将中点反转后
slow = reverse(slow);
fast = head;
while(slow != null) {
if(slow.val != fast.val)
return false;
slow = slow.next;
fast = fast.next; }
return true;
}
public ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode next = null;
while(head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}