［抄题］：
设计一种方式检查一个链表是否为回文链表。1->2->1 就是一个回文链表。
[暴力解法]：
时间分析：
空间分析：
［思维问题］：
以为要从从后往前扫描，不知道调用reverse函数。其实找中点、翻转都是链表中直接能用的API
［一句话思路］：
后半截儿反过来以后，相同就同时走。走到头说明一直相等，没走到头说明有不相等的地方。
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- middle.next = reverse(middle.next); 作用于谁就给谁
- 两个指针同时走且要求值相等时，养成按逻辑顺序写的习惯：必须先判断非空 再判断相等p2 != null && p1.val == p2.val
［二刷］：
［三刷］：
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
［总结］：
［复杂度］：Time complexity: O(n) Space complexity: O(1)
还是原来的链表，只是后半截儿反过来了，所以还是1
［英文数据结构或算法，为什么不用别的数据结构或算法］：
［关键模板化代码］：
private ListNode findMiddle(ListNode head) {
// corner case
if (head == null) {
return null;
}
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode reverse(ListNode head) {
// corner case
if (head == null) {
return null;
}
ListNode prev = null;
while (head != null) {
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
middle-快慢，reverse-四步走
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
[代码风格] ：
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/ public class Solution {
/**
* @param head: A ListNode.
* @return: A boolean.
*/
public boolean isPalindrome(ListNode head) {
// corner case
if (head == null) {
return true;//true
}
//p1 go with p2
ListNode middle = findMiddle(head);
middle.next = reverse(middle.next);// ListNode p1 = head, p2 = middle.next;
while (p2 != null && p1.val == p2.val) {//order
p1 = p1.next;
p2 = p2.next;
}
return p2 == null;
} private ListNode findMiddle(ListNode head) {
// corner case
if (head == null) {
return null;
}
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
} private ListNode reverse(ListNode head) {
// corner case
if (head == null) {
return null;
}
ListNode prev = null;
while (head != null) {
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
}