?作者簡介：大家好，我是車神哥，府學路18號的車神?

?個人主頁：應無所住而生其心的博客_府學路18號車神_CSDN博客
?點贊?評論?收藏 == 養成習慣（一鍵三連）?
?本系列主要以刷LeetCode（力扣）網站的各類題為標準，實現自我能力的提升為目標?
?希望大家多多支持?~一起加油 ?

• 專欄《LeetCode天梯》

周四，今天中午終于擁有了一個久違的午休了，老黃說我睡到打呼嚕，連續加班幾天了，趕項目，做實驗，寫論文，哎，對了，官方送的CSDN的水杯到了，應該是C站人手一個吧，哈哈哈，一杯茶，坐下就是一下午，加油吧！

每天進步一點點，就已經很棒很棒了，堅持堅持，不要太累，拒絕內卷，從每日一練開始，每天十分鐘，快樂生活一輩子！疫情依舊反復，大家帶好口罩啊~ 繼續繼續，來，今天和車神哥一起來提升自己的Python編程和面試能力吧，刷天梯~

放上我拍的Photo吧！~

每日推薦一首歌：夏天的風——火羊瞌睡了

以下為我的天梯積分規則：

每日至少一題：一題積分+10分
若多做了一題（或多一種方法解答），則當日積分+20分（+10+10）
若做了三道以上，則從第三題開始算+20分（如：做了三道題則積分-10+10+20=40；做了四道題則積分–10+10+20+20=60）

---

初始分為100分
若差一天沒做題，則扣積分-10分（周六、周日除外注：休息）
堅持！！！

初級算法

刷題目錄

鏈表

題干

給你一個單鏈表的頭節點 head ，請你判斷該鏈表是否為回文鏈表。如果是，返回 true ；否則，返回 false 。

示例1：

輸入：head = [1,2,2,1]
輸出：true

示例2：

輸入：head = [1,2]
輸出：false

提示：

• 鏈表中節點數目在范圍[1, 105] 內
• 0 <= Node.val <= 9

雙指針（反轉后半部分鏈表）

分析：

首先要明白一點回文鏈表是什么，回文鏈表就是以鏈表中間為中心點兩邊對稱。
平時比較常見的是字符串回文串，我們使用雙指針，一直指向首，另一個指向尾部，這樣往中間一直走一直比對，全部相同則返回True，不同則False。
由于本題判斷的是鏈表，且是單向鏈表，只能從前往后訪問，不能從后往前訪問，所以使用判斷字符串的那種方式是行不通的。
但是我們可以通過首先尋找到中間的節點，然后再將后半部分節點進行反轉操作，再將兩半部分鏈表進行比對就OK了。

具體的借用下大佬的圖：

class Solution:    def isPalindrome(self, head: ListNode) -> bool:        # 雙指針        fast = head        slow = head        if not head or not head.next:            return True        # 若fast不為空值，則鏈表的長度為奇數        # if fast != None:        #     slow = slow.next        # 反轉后半部分鏈表        def reversenode(head):            out = None            while head:                next = head.next                head.next = out                out = head                head = next            return out                # 通過快慢指針找到中點        while fast  and fast.next:            fast = fast.next.next            slow = slow.next        slow = reversenode(slow)        # fast = head        while slow and head:            # 依次比較節點值是否相同            if head.val != slow.val:                return False            # else:            head = head.next            slow = slow.next        return True

真的，真的，真的好慢呀！~

遞歸法

再試試遞歸法~

可以對鏈表逆序操作：

def reverseListNode(head):	if head == None:		return  # 終止條件	pre = None	pre = reverseListNode(head.next)	return pre

引用一下官方的代碼（主要是較為優雅），直接上代碼：

class Solution:    def isPalindrome(self, head: ListNode) -> bool:       # 遞歸        self.front_pointer = head        def re_check(current_node=head):            if current_node is not None:                if not re_check(current_node.next):                    return False                if self.front_pointer.val != current_node.val: # 比較                    return False                self.front_pointer = self.front_pointer.next            return True        return re_check()

說實話，這個遞歸更慢，下面再試一下棧！遞歸有點難以理解，建議慢慢思考！~

棧

利用先進后出的思想，將其放在棧中，然后再一個一個出站，就實現了鏈表從后往前訪問了。

其中還可以用一個簡單的，將鏈表的值放在list中，再對數組進行反轉，再比對反轉后有無相同。

先實現棧操作：

遍歷鏈表，把每個節點都Push進stack中；然后再遍歷鏈表，同時節點依次出棧，二者進行比較。

class Solution:    def isPalindrome(self, head: ListNode) -> bool: 		stack = []        # Push 操作        current_node = head        while current_node:            stack.append(current_node)            current_node = current_node.next        # POP + Compare 刪除和比較        node = head        while stack:            node2 = stack.pop()  # 刪除最后一個，將其刪除值賦值給node2            if node.val != node2.val:                return False            node = node.next        return True

利用棧操作，比遞歸快很多，哈哈哈！

鏈表轉數組比對

接著上面的，我們可以將鏈表值直接存入新的數組中，然后再對數組反轉，將二者進行比對，如果相同則True，否則False。

這思想好像是最簡單的了！！！

哈哈哈

class Solution:    def isPalindrome(self, head: ListNode) -> bool:  		# 數組        sav = []             # 設置空list        while head:         # 存入list            sav.append(head.val)            head = head.next        return sav == sav[::-1]

速度又提升了耶！~

今天用了四種方法，加油呀！！

準備又要開始做論文實驗了o(╥﹏╥)o，誰來幫幫我呀！~

Reference

作者：力扣 (LeetCode)
鏈接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnarn7/
來源：力扣（LeetCode）

今日得分：+10+10+20+20
總得分：590

加油！！！

?堅持讀Paper，堅持做筆記，堅持學習，堅持刷力扣LeetCode?！！！
堅持刷題！！！打天梯！！！
?To Be No.1

??哈哈哈哈

---

?創作不易?，過路能?關注、收藏、點個贊?三連就最好不過了

?( ′???` )

?

『
我從來不相信什么懶洋洋的自由，我向往的自由是通過勤奮和努力實現的更廣闊的人生，那樣的自由才是珍貴的、有價值的；我相信一萬小時定律，我從來不相信天上掉餡餅的靈感和坐等的成就。做一個自由又自律的人，靠勢必實現的決心認真地活著。
』