3.2　回文链表

链表相对于字符串来说难度会增加一点，但其实二者都属于线性数据结构，因此难度也只表现在写法上，在思路上并没有增加太大的难度。

题目描述（第234题）

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

示例1

输入：1→2

输出：False

示例2

输入：1→2→2→1

输出：True

进阶

你能否用O(n)时间复杂度和O(1)空间复杂度解决此题？

思路

这是一道Amazon的面试题，难度级别为简单，是一道热身题。链表不同于数组（字符串本质上是字符数组），不支持随机访问。对于单链表来说，只有一个指向下一个节点的指针。如果不考虑复杂度，可以将链表进行一次遍历，遍历的同时将值放到一个数组中，然后可以采用字符串的思路去解决。这种算法需要额外的数组存储链表的值，因此这种算法的空间复杂度是O(n)。空间上可以进一步优化。下面介绍一种空间复杂度为O(1)的解法。

首先使用快/慢指针的技巧找到中点，找到中点的同时将前半部分链表进行反转。然后将慢指针和慢指针的前一个指针同时移动，如果两者指向的数字有一个不同则说明不是回文，否则则是回文。这里有两个要点。

●　如何找到中点？我们只需要建立快/慢指针，快指针fast每次走两步，慢指针slow每次走一步。这样当快指针走到终点时，慢指针刚好走到中间位置。

●　如何进行反转？其实链表反转是一个单独且常见的考点，力扣（LeetCode）上也有原题（第206题反转链表，见参考链接/正文[8]）。我们使用一个变量记录前驱pre，一个变量记录后继next，不断更新current.next=pre就好了。

反转链表的代码如下所示。

找到中点时链表情况如下图所示。

之后pre和slow分别向前、向后遍历即可。当然这里的“向前”本质上还是借助于next指针移动，只不过我们已经对前半部分进行了反转，因此可以通过next找到前驱节点。

代码

复杂度分析

●　时间复杂度：算法由两部分组成。第1部分是找到中点，这部分的时间复杂度为O(n)；第2部分是从中点分别向左和向右移动，这部分的时间复杂度同样是O(n)，因此总的时间复杂度为O(n)，其中n为节点数。

●　空间复杂度：O(1)。