LeetCode 234 Palindrome Linked List
=================================
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?
对于判断palindrome的问题，一般思路有两种：
- 分别设头指针与尾指针，判断头尾是否相等直到中间点。由于本题是单链表，需要用一些trick完成链表的反向搜索
- 将palindrome从中间截断，形成两个字符串（或链表），reverse其中的一个，判断两个字符串（或链表）是否相等
思路一：
扫描一遍单链表，将其转化为ArrayList，之后用头尾指针判断ArrayList是否为回文。
时间复杂度O（N），空间复杂度O（N）。
思路二：
用快慢指针扫描一遍单链表，慢指针最终会停在链表中间（快慢指针法适用于求链表重点，判断链表是否有环等问题）。扫描的同时将链表的前半部分放入stack中。当快指针到达尾部后，再一一比较放入stack的前部分与slow开始的后半部分，此时stack的出栈变可以巧妙地完成链表的反向搜索。
需要注意的是，如何判断list的结点数量是奇数个的方法。如果最后fast!=null的话，说明是奇数个。
时间复杂度O（N），空间复杂度O（N）。
思路三：
若要求时间复杂度O（N），空间复杂度O（1），则可将慢指针开始的后半链表反向，比较前半部分与反向后的后半部分，是否一一相等。
这里需要注意reverse(ListNode head)的方法，是转置以head开头的链表，但是并不改变head的前一个结点的next一直指向head。所以，无论右半段如何转置，前一个结点都不会变，也不会引起死循环。
/**
* 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 fast = head, slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 奇数个结点
if(fast != null) {
slow = slow.next;
}
// 右半侧反向
ListNode right = reverse(slow);
ListNode left = head;
boolean res = true;
ListNode helper = right;
while(right != null) {
if(left.val != right.val) {
res = false;
break;
}
//left的最后一个节点（即中间点的前一个节点），仍然指向中间点
//因此奇数情况下，最后一次循环left与right都指向中间点
left = left.next;
right = right.next;
}
// 恢复右半侧
reverse(helper);
return res;
}
public ListNode reverse(ListNode head) {
ListNode pre = null;
while(head != null) {
ListNode next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
