今天是 2020 年 02 月 02 日，被称为「千年一遇的对称日」，20200202 正反都一样，反正都是「爱你爱你」的意思。不少新人都选择今天作为领证的日子，不过因为肺炎的缘故，有些地方已经取消了今日的预约。
但是我们今天不聊这日子的寓意，我们来聊聊技术相关的话题。
20200202 这种正反都一样的串，在算法上称为「回文」，又因为不同的结构，被分为回文数、回文字符串、回文链表等。
这分别又延伸出好几个 Leetcode 算法题，今天我们在这个别人领证的日子，复习一下回文相关的算法题。
一. 验证回文字符串
今天的日期，用字符串表示是 "20200202"，这就是一个回文字符串。
那么想要写个方法，验证其是否是一个回文字符串，拍脑袋想最简单的方法就是将字符串翻转后比对。
但是多数情况下是不允许我们直接使用 Api，那除此之外，比较常用的方法就是用 2 个指针，从字符串的前后两个方向，向内夹。
逻辑很简单，一个循环两个指针，就搞定了。
但是因为这是一个字符串，很轻易的可以拿到字符串的长度，所以一般算法题会加上一些额外的条件，增加难度。
例如 Leetcode 上的「125. 验证回文串」，给定的字符串是包含空格的。
这种情况呢，只需要把之前的解法改改就好了，两个指针在移动的时候，如果遇上 1 个空格就多走 1 步即可。
通过 isLetterOrDigit() 可以直接判断当前字符是不是只属于字母和数字。
关于字符串的回文算法，除了 125 之外，leetcode 上第 680 题也属于回文字符串，有兴趣可以去看看。
二. 验证回文数
如果回文字符串中只包含数字，那么它也可以是一个回文数，例如 20200202。
想要验证回文数，比较简单的方法就是将其转换字符串，然后用验证字符回文串的算法模式去套用。但是这并没有用到数字的特性。
既然是数字，我们可以通过除法 / 和取余 % 的方式，将这个数字取出后半段进行翻转，然后比对两个数字的是否相等。
简单解释一下：
1. 首先做一些简单的验证。如果一个大于 0 的非零数，个位为 0 ，那么它注定不是一个回文数。因为对应的回文位置是这个数字的最高位，而最高位不会为 0。
2. 通过循环，每次循环中，按位生成翻转后的数字，并将原数字最低位打掉。
3. 如果跳出循环，说明后半部分已经翻转完毕，那么分两个情况考虑，数字长度是奇数还是偶数。然后判断原数字 x 和后半部分翻转的数字 reversedNumber 是否相同。
另外提一句，这道题是 Leetcode 上的「9. 回文数」题。
三. 验证回文链表
回文串和回文数都说了，接下来看看回文链表。
单链表这种特殊的结构，想要确定个长度也需要 O(n) 的复杂度，而且没有前驱指针，双指针前后夹的办法是没法用了。
当然我们可以将它转换为我们熟悉的回文数或者回文串进行计算，但是这同样没有用到链表的特性。
在验证回文链表的场景下，我们可以通过快慢指针的方式找到链表的中间节点，然后再将原链表的一半反转，之后开始比对。
为了效率，可以把这两个步骤糅合在 1 个循环中。
第一遍循环之后，slow 节点指向了链表的中间位置，而 pre 则是翻转了原链表的前半部分的子链表。
再通过一个 while 循环，将它们逐个比对，就可以得到我们要的结果。
另外提一句，这道题是 Leetcode 上的「234. 回文链表」题。
四. 小结时刻
那今天就到这里，20200202 这个日子里，我们复习了一下回文相关的算法题，不知道分别从字符串、数字、链表三个方向横向的看回文类的题之后，你能总结出什么规律？欢迎在留言去讨论。
因为肺炎的缘故，不少朋友明日起就要开启在家办公的状态，祝各位顺利。
本文对你有帮助吗？留言、转发、点赞是最大的支持，谢谢！
在头条号私信我。我会送你一些我整理的学习资料，包含：Android反编译、算法、设计模式、虚拟机、Linux、Kotlin、Python、爬虫、Web项目源码。
閱讀更多 承香墨影 的文章
