234-回文链表

请判断一个链表是否为回文链表。

示例 1:　输入:1->2   　　　　输入:1->2->2->1

　　　　输出:false　　　　  输出:true

自己实现使用一个vector，保存每一个值，再判断是不是回文。

代码

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？－>原文

要使用O(1)的空间复杂度，我们只能在给出的链表身上做文章。我们首先找到链表的中点，然后将中点后的链表反转，再与前面的节点进行比较。

这里对代码进行一下解释，第一个while循环是通过快慢指针找到链表的中点，慢指针每次走一步，快指针每次走两步，当快指针到达链表结尾时，慢指针即指向链表中点。

第二个while循环是对中点后面的链表部分进行反转，以链表1,2,3,4,4,3,2,1为例，每次对后面链表进行一次调整，具体过程图解如下：

反转过程

得到反转后的链表后，第三个while就不用多说了，循环比较两个链表对应位置元素即可。