【Leetcode刷题Python】234.回文链表

简介: 两种判断链表是否为回文的方法:使用栈和拆分为两个链表后反转对比,并给出了相应的Python代码实现。

1 题目

请判断一个链表是否为回文链表。

比如【1】【1,2,2,1】【1,2,1】,【1,2,3,3,2,1】

2 解析

(1)方法一:使用栈

将前一半入栈,然后出栈,对比后一半的元素,注意如果链表长度是奇数,就需要跳过中间元素。

(2)方法二:拆分为两个链表,反转后半段链表,再依次对比

注意:找到中间元素,可以用计数法或者快慢指针法,以下我用是计数法。

3 Python实现

(1)方法一

# 方法一:使用栈
def isPalindrome(self, head: ListNode) -> bool:
   stack = []
   count = 0
   cur = head
   curr = head 
   # 统计链表的元素个数
   while cur:
       count+=1
       cur = cur.next
   # 一半进栈
   for _ in range(int(count/2)):
       stack.append(curr)
       curr = curr.next
   # 如果是奇数,跳过中间那个元素,不对比
   if count%2!=0:
       curr = curr.next
   # 一次对比每个元素
   while curr and stack:
       tmp = stack.pop()
       if tmp.val !=curr.val:
           return False
       else:
           curr = curr.next
   return True

(2)方法二

# 方法二:
def isPalindrome(self, head: ListNode) -> bool:
   prev = head
   end = head
   count = 0
   cur = head
   # 统计链表的元素个数
   while cur:
       count+=1
       cur = cur.next
   # 只有一个元素,直接判断为回文
   if count==1:
       return True
   # 指针移动到一半
   for _ in range(int(count/2)-1):
       end = end.next
   # 将前半段链表和后半段链表分开
   next = end.next
   end.next = None
   # 如果是奇数,跳过中间元素,不对比 
   if count%2!=0:
       next = next.next
   # 反转后面个链表
   newlink = self.reveseList(next)
   curr = newlink 
   # 对比两个链表
   while curr: 
       if curr.val != prev.val:
           return False
       curr = curr.next
       prev = prev.next
   return True
def reveseList(self,head:ListNode)->ListNode:
   prev,curr = None,head
   while curr:
       next = curr.next
       curr.next = prev
       prev = curr
       curr = next
   return prev
目录
相关文章
|
2月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
36 1
|
2月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
50 0
Leetcode第21题(合并两个有序链表)
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
28 1
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
2月前
|
搜索推荐 Python
Leecode 101刷题笔记之第五章:和你一起你轻松刷题(Python)
这篇文章是关于LeetCode第101章的刷题笔记,涵盖了多种排序算法的Python实现和两个中等难度的编程练习题的解法。
23 3
|
2月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
22 0
LeetCode第二十四题(两两交换链表中的节点)
|
2月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
44 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
2月前
|
算法 C++ Python
Leecode 101刷题笔记之第四章:和你一起你轻松刷题(Python)
这篇博客是关于LeetCode上使用Python语言解决二分查找问题的刷题笔记,涵盖了从基础到进阶难度的多个题目及其解法。
18 0
|
2月前
|
算法 C++ Python
Leecode 101刷题笔记之第三章:和你一起你轻松刷题(Python)
本文是关于LeetCode算法题的刷题笔记,主要介绍了使用双指针技术解决的一系列算法问题,包括Two Sum II、Merge Sorted Array、Linked List Cycle II等,并提供了详细的题解和Python代码实现。
15 0