今天是 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項目源碼。
閱讀更多 承香墨影 的文章
