原题链接在这里：

题目：

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?

题解：

原题要求time O(n), space O(1). 所以不能用额外空间。

先找到中点, reverse中点后面的list部分，再与head开始逐个比较val. 其中reverse部分可以参见.

Time Complexity: O(n). Space O(1).

AC Java:

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 class Solution {10     public boolean isPalindrome(ListNode head) {11         if(head == null || head.next == null){12             return true;13         }14         15         ListNode mid = findMid(head);16         ListNode midNext = mid.next;17         mid.next = null;18         19         midNext = reverse(midNext);20         21         while(head != null && midNext != null){22             if(head.val != midNext.val){23                 return false;24             }25             26             head = head.next;27             midNext = midNext.next;28         }29         30         return true;31     }32     33     private ListNode findMid(ListNode head){34         if(head == null || head.next == null){35             return head;36         }37         38         ListNode runner = head;39         ListNode walker = head;40         while(runner.next != null && runner.next.next != null){41             walker = walker.next;42             runner = runner.next.next;43         }44         45         return walker;46     }47     48     private ListNode reverse(ListNode head){49         if(head == null || head.next == null){50             return head;51         }52         53         ListNode tail = head;54         ListNode cur = tail;55         ListNode pre;56         ListNode temp;57         while(tail.next != null){58             pre = cur;59             cur = tail.next;60             temp = cur.next;61             cur.next = pre;62             tail.next = temp;63         }64         65         return cur;66     }67 }