题目：
leetcode 234. Palindrome Linked List(easy)
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?
题目大意：
判断一个链表是否是回文链表。
进阶：用时间复杂度O(n)和空间复杂度O(1)解题
解题思路：
这道题本质上也是考察反转链表的内容，属于反转链表的应用。
将链表均分成两半，把后一半反转，再判断相等即可，所以说翻转链表是一项很基础的工具算法，为很多其他的算法提供思路，须重点掌握。
下面代码中求链表中点的方法也非常值得记忆！
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44Java:
public boolean isPalindrome(ListNode head){
if(head == null || head.next == null) return true;
ListNode slow = head,fast = head;
while(fast != null && fast.next != null){ //fast!=null 不能缺少，否则没法获得链表个数是奇数的情况
fast = fast.next.next;
slow = slow.next;
//fast每次走两步，slow每次走一步，所以fast走完(奇数或偶数)时，slow刚好到中点(奇数情况)或中点的下一个(偶数情况,第二个链表开始的节点)
}
if(fast!= null) slow = slow.next;//链表个数是奇数的情况，slow再往后走一步，指向第二个链表开始的节点
cut(head,slow);
return isEqual(head,reverse(slow));
}
private void cut(ListNode head,ListNode cutnode){
while(head.next != cutnode){ // !! head.next不等于cutnode,不是head不等于cutnode!! head是第一个结点的最后一个节点
head = head.next;
}
head.next = null;
}
private ListNode reverse(ListNode head){
ListNode newHead = null;
while(head != null){
ListNode nextnode = head.next;
head.next = newHead;
newHead = head;
head = nextnode;
}
return newHead;
}
private boolean isEqual(ListNode l1,ListNode l2){
while(l1 != null && l2 != null){
if(l1.val != l2.val) return false;
l1 = l1.next;
l2 = l2.next;
}
return true;
}
Python:
