Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
这个follow up要求O(n)的时间和O(1)的空间，可以先reverse一半，然后再对比。只是reverse的时候要考虑奇数个还是偶数个。如果是奇数个的话，就跳过最中间的，从下一个开始reverse。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isPalindrome(ListNode head) {
ListNode runner = head;
ListNode walker = head;
while (runner != null && runner.next != null) {
runner = runner.next.next;
walker = walker.next;
}
ListNode half = runner == null ? reverse(walker): reverse(walker.next);
while (half != null) {
if (head.val != half.val) {
return false;
}
half = half.next;
head = head.next;
}
return true;
}
private ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode node = head.next;
ListNode newHead = reverse(node);
node.next = head;
head.next = null;
return newHead;
}
}
Palindrome Linked List Leetcode
原文：http://www.cnblogs.com/aprilyang/p/6959314.html