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

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

• 專欄《LeetCode天梯》

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

每天進(jìn)步一點點，就已經(jīng)很棒很棒了，堅持堅持，不要太累，拒絕內(nèi)卷，從每日一練開始，每天十分鐘，快樂生活一輩子！疫情依舊反復(fù)，大家?guī)Ш每谡职 繼續(xù)繼續(xù)，來，今天和車神哥一起來提升自己的Python編程和面試能力吧，刷天梯~

放上我拍的Photo吧！~

每日推薦一首歌：夏天的風(fēng)——火羊瞌睡了

以下為我的天梯積分規(guī)則：

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

---

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

初級算法

刷題目錄

鏈表

題干

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

示例1：

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

示例2：

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

提示：

• 鏈表中節(jié)點數(shù)目在范圍[1, 105] 內(nèi)
• 0 <= Node.val <= 9

雙指針（反轉(zhuǎn)后半部分鏈表）

分析：

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

具體的借用下大佬的圖：

class Solution:    def isPalindrome(self, head: ListNode) -> bool:        # 雙指針        fast = head        slow = head        if not head or not head.next:            return True        # 若fast不為空值，則鏈表的長度為奇數(shù)        # if fast != None:        #     slow = slow.next        # 反轉(zhuǎn)后半部分鏈表        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:            # 依次比較節(jié)點值是否相同            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

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

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()

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

棧

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

其中還可以用一個簡單的，將鏈表的值放在list中，再對數(shù)組進(jìn)行反轉(zhuǎn)，再比對反轉(zhuǎn)后有無相同。

先實現(xiàn)棧操作：

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

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

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

鏈表轉(zhuǎn)數(shù)組比對

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

這思想好像是最簡單的了！?。?/p>

哈哈哈

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

速度又提升了耶！~

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

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

Reference

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

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

加油！??！

?堅持讀Paper，堅持做筆記，堅持學(xué)習(xí)，堅持刷力扣LeetCode?！?。?br /> 堅持刷題！??！打天梯！?。?/strong>
?To Be No.1

??哈哈哈哈

---

?創(chuàng)作不易?，過路能?關(guān)注、收藏、點個贊?三連就最好不過了