判断链表是回文

首先，我们要搞明白什么是回文，举个简单的例子，单链表 0 -> 1 -> 2 -> 1 -> 0 就是回文，具体说来就是正着看和反着看是一样的。

从这个定义出发，我们可以得到第一种解决方案：反转比较法。

将单链表反转，然后和原来的进行比较，如果两者一致，那么该单链表表示的内容是回文，否则就不是。

但是比较的时候不用比较全部链表，只需要比较到一半就可以了。因为反转链表的后半段就是原链表的前半段，反转链表的前半段就是原链表的后半段，两段是等价的，所以只需比较一半即可。

原问题等价于链表的前半段是否是链表的后半段的反转。

如何解决等价问题呢？把前半段反转的形式存起来，再遍历即可。恰巧栈 Stack 这种数据结构就是专门来做这事的。于是，我们得到了第二种解决方案。

第一个阶段是把前半段放到一个栈里面，第二阶段是比较后半段和栈中的内容是否一致。

现在问题来了，如果不知道链表的长度，咋知道第一阶段结束了呢？使用快慢指针的方法。

这里提一下，这种方法真是解决单链表问题的制胜法宝，很多问题都可以用到。

把慢指针的内容放入栈中，当快指针走到头的时候，那么慢指针刚好把一半的内容放入栈中。这里要注意以下，如果长度是奇数，也就是 fast.Next.Next == null，但是 fast.Next != null，需要把慢指针再向前一步。对于回文来说，正中间位置的内容不影响判断的结果。好了，第一阶段的内容做完了，第二阶段很容易，一个 while 循环就好了。