判断一个链表是否为回文结构
给定一个链表的头节点head，请判断该链表是否为回文结构。
例如：1 ->2 -> 1，返回true。1 -> 2 -> 2 -> 1，返回true。15 -> 6 -> 15，返回true。1 -> 2 -> 3，返回 false 。
进阶: 如果链表长度为N,时间复杂度达到O(N),额外空间复杂度达到O(1)
法一： List 节点全部入栈
将链表 List 节点依次压入栈中，利用栈的先进先出性质，依次遍历链表（从head开始遍历）的同时弹出栈顶，如果弹出的节点node与所遍历的链表node相同就继续，不同则结束，表示链表不是回文结构。
网络异常，图片无法展示
|
时间复杂度：需要遍历整个 List ，所以 T(n) = O(n)
空间复杂度：由于需要保存 List 的所有节点，所以 S(n) = O(n)
法二：快慢指针法，一半的List 节点入栈
利用“回文”两字的概念：回文结构的链表是关于中间的对称轴对称的。因此可以只将链表右边部分入栈。
思路
- 快指针 A 一次走 2 步，慢指针 B 一次走 1 步；当 A 走到 List 末尾时， B 刚好到中点；
- B 将后半部分遍历并压入栈中；
- A 再从头开始遍历，每遍历一个，栈 pop 一个进行比较。
- 某一步不相等 => false；遍历结束后且之前未返回 => true 。
细节
- 对于奇偶数，边界值的取值差异
- 如何保证只是右边部分进栈？——双指针
时间复杂度：需要遍历整个 List ，所以 T(n) = O(n)
空间复杂度：仅需要保存 List 的后半部分节点，相比法一少了一半，但是去除系数，S(n) = O(n)
法三：快慢指针升级版，右边部分逆序，降低空间复杂度至O(1)
这里我们才不借助辅助空间。首先我们能找到 List 的中点，让 List 一分为二，并让后半部分逆序；接着前半部分从前往后，后半部分从后往前遍历，边遍历便比较。如此，两个 node 的空间即解决了问题。
思路
- 快指针 A 一次走 2 步，慢指针 B 一次走 1 步；当 A 走到 List 末尾时， B 刚好到中点；
- 将中点的 next 指向 null ，右部分逆序；
- 两个 list 都从首开始遍历比较，直到结束。
- 得到 true / false 的结果后，记得将原结构恢复 。
细节
用 length-1 来计算：奇数个节点，中点指向null ；偶数个节点，慢指针会来到中点的前一个位置。如下图：
网络异常，图片无法展示
|
面试时关于链表解题的方法论
- 对于笔试，不用太在乎空间复杂服，一切为了时间复杂度
- 对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法
比如拿本文这个题目来说，如果是笔试，直接使用法一；如果是面试，第一二方法大家都能想到，面试时面试官想看到的是第三种方法。
知识点
- 如何获取链表中间节点
- 反转链表
