算法题学习 --- 判断一个链表是否为回文结构
题目
描述
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 0≤n≤10^5，链表中每个节点的值满足∣val∣≤10^7
示例 1
示例 2
示例 3
分析
考虑特殊情况
在进行问题分析过程前，我们先考虑一下特殊情况，那么在这道问题中，有哪些情况是特殊的呢？
不难发现，如下情况：
head 为空指针或 head->next 为空指针时，说明该链表没有元素或只有一个元素，此时无需判断，该链表属于回文结构。
考虑一般情况
通过题目中对回文结构的定义，我们先抛开链表的形式，如果是数组的形式，那么我们就可以使用两个 index，一个从前往后，一个从后往前，遍历直到相遇，检查每一个数值是否相等，如果都相等，那说明是回文结构，如果中间有不相等的，那就不是回文结构。
再回到我们的链表结构，明显地，我们有两个问题需要解决：
1.如何将链表分为两个部分？
这里我们可以使用快慢指针的方式，快指针每次走两步，慢指针每次走一步，这样，当快指针走到末尾时，慢指针恰好指向中点。
或者我们先遍历一次链表得到链表的长度，然后除二，从头走对应的步数也能找到对应的节点
2.将链表的后半部分反转
这里我们可以使用之前的插入方式，进行链表的反转。
step 1：遍历链表，统计链表的长度。
step 2：将长度除 2，遍历这么多位置，找到链表的中点。
step 3：从中点位置开始，对链表后半段进行反转。
step 4：与方法二类似，双指针左指针指向链表开头，右指针指向链表尾，此时链表前半段是正常的，我们也可以正常遍历，但是链表后半段所有指针都被我们反转逆序，因此我们可以从尾节点往前遍历。
step 5：依次比较对应位置的元素值是否相等。
代码示例
这里使用的是双指针找中点+链表反转的方法。
版权声明: 本文为 InfoQ 作者【桑榆】的原创文章。
原文链接:【http://xie.infoq.cn/article/3c3e3ef1bf21df455c417b5aa】。文章转载请联系作者。
北海虽赊，扶摇可接；东隅已逝，桑榆非晚！ 2020-02-29 加入
Android手机厂商-相机软件系统工程师 爬山/徒步/Coding
评论