給你一個單鏈表的頭節點 head ，請你判斷該鏈表是否為回文鏈表。如果是，返回 true ；否則，返回 false 。示例 1：輸入：head = [1,2,2,1] 輸出：true 示例 2：輸入：head = [1,2] 輸出：false思路:可以用快慢指針 + 反轉鏈表解決。使用快慢指針找到鏈表的中間位置，然后將鏈表分為兩個部分 反轉后半部分鏈表 逐一對比前后兩部分鏈表 恢復鏈表 返回結果注意:如果鏈表長度是偶數的話，前半部分和后半部分長度是一樣的。如果鏈表長度是奇數，那么 前半部分的長度比后半部分長度多 1 個，所以最后迭代鏈表的時候，以后半部分為準就可以了，當 鏈表總長為奇數時，前半部分的最后一個節點就不會被遍歷到了。# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution:def isPalindrome(self, head: ListNode) -> bool:# 方法一# res = []# current = head# while current:# res.append(current.val)# current = current.next# return res == res[::-1]# 方法二if head is None:return True# 找到前半部分鏈表的尾節點并反轉后半部分鏈表first_half_end = self.end_of_first_half(head)second_half_start = self.reverse_list(first_half_end.next)# 判斷是否回文result = Truefirst_position = headsecond_position = second_half_startwhile result and second_position is not None:if first_position.val != second_position.val:result = Falsefirst_position = first_position.nextsecond_position = second_position.next# 還原鏈表并返回結果first_half_end.next = self.reverse_list(second_half_start)return result def end_of_first_half(self, head):fast = headslow = headwhile fast.next is not None and fast.next.next is not None:fast = fast.next.nextslow = slow.nextreturn slowdef reverse_list(self, head):previous = Nonecurrent = headwhile current is not None:next_node = current.nextcurrent.next = previousprevious = currentcurrent = next_nodereturn previous

總結

以上是生活随笔為你收集整理的34. Leetcode 234. 回文链表 (链表-双指针)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。