0234. Palindrome Linked List (Easy)
Question
Given a singly linked list, determine if it is a palindrome.
Example 1
| |
Example 2
| |
Follow up:
Could you do it in O(n) time and O(1) space?
分析/解題
給定一個單向鏈結串列，試判斷它是否是palindrome(回文)。
所謂palindrome就是從尾到頭和從頭到尾看起來會相同 。
在這題當中，由於我們的結構是Linked List，無法很輕鬆的到達尾端，
也無法輕易的回頭，那麼該怎麼辦呢？
要判斷回文有一個重點，就是從中間切開來兩邊是對稱的 。
因此，我們可以設定fast/slow的兩個pointer，
以之前常用的技巧，每次fast走兩步，slow走一步 ；
讓fast走到底時，slow剛好走到一半 。
節點總數是偶數時，切開來的第二段應該是從slow的下一個節點 開始，
所以當fast不是NIL 時，我們應該讓slow多走一步 。
(例如總共有10個節點，按上面的方法走完，
fast會在10，slow會在5，但第二段應該從6開始，所以slow要往下走一步)
所以比較「從slow到串列尾端的反轉串列 」及
「從head往下的對應節點 」，即可檢驗串列是否為回文。
那麼要怎麼反轉串列呢？上上篇文章 不就是嗎XD
我們可以用之前的reverse函數進行反轉，
反轉後再對兩個串列一一進行比較，
一旦值不相等即回傳false。
依此，寫成程式碼如下：
Java
我們也可以使用另一種思路，
先多設定一個rev節點，
在slow/fast行進時，將slow經過節點進行反轉連接，
這樣在走完的時候，讓rev 變成前半段反轉後的串列的開頭 ，
而slow 則是後半段的串列的開頭 。最後同樣一個一個檢查，
即可判斷整個串列是否是回文。
Python
務必請留意這麼做的缺點是整個串列就被我們拆成兩半了 ，
如果不是要求空間複雜度是O(1)的話，
用別的資料結構輔助去存入一半的節點，能夠保有原先的結構。
面試實際可能會遇到的問題
「時間/空間複雜度？」
(O(N)/O(1))
「如果不計較空間複雜度，有沒有辦法保留原先的linked list呢？」
(Python的話可以使用list來做兩邊儲存比較的動作，
或者要使用stack來置入前半段的節點，後面pop出來做比較也可以)
相似及延伸
Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)
從LeetCode學演算法，我們下次見囉，掰~
感謝大家對這系列文章的支持！這邊跟大家自我工商一下：
筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium限額5名優惠(額滿即截止)： https://hiskio.com/courses/319?promo_code=VE9NJQE
問卷抽書＆取得上架通知： https://pse.is/MS2J2
如果你對線上課程不放心，
也可以先來12/17(二) 我在天瓏分享的講座看看！
講座連結： https://pse.is/JS3LJ