博客主页:🏆看看是李XX还是李歘歘 🏆
🌺每天分享一些包括但不限于计算机基础、算法等相关的知识点🌺
💗点关注不迷路,总有一些📖知识点📖是你想要的💗
⛽️今天的内容是 Leetcode 234. 回文链表 ⛽️💻💻💻
234. 回文链表
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
示例 1:
输入:head = [1,2,2,1]
输出:true
示例 2:
输入:head = [1,2]
输出:false
提示:
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
876. 链表的中间结点、Leetcode的Go实现_李歘歘的博客-CSDN博客
206. 反转链表、Leetcode的Go实现_李歘歘的博客-CSDN博客
使用206的反转方法,回文串反转后其值与原来一样:
注意:不可以在反转的链表和原链表是直接进行比较,因为链表是有地址的:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
tmp = None
res = None
while head is not None :
tmp = head.next
head.next = res
res = head
head = tmp
return res
def isPalindrome(self, head: ListNode) -> bool:
orgList,revList = [],[]
temp = head
# 存储链表元素
n = temp
while n is not None:
orgList.append(n.val)
n = n.next
# 反转链表
reve = self.reverseList(head)
# 存储链表元素
m = reve
while m is not None:
revList.append(m.val)
m = m.next
# 链表不能直接比较其值(我们值关注链表中的val,当地址不同时也返回false)
return orgList == revList
先遍历链表,值保存在slice,后判断slice是否回文:此处省略
找链表中点,反转后半部分,对比:文章来源:https://www.toymoban.com/news/detail-737989.html
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
tmp = None
res = None
while head is not None :
tmp = head.next
head.next = res
res = head
head = tmp
return res
def isPalindrome(self, head: ListNode) -> bool:
# 快慢指针找中点
slow, fast = head,head
while fast is not None and fast.next is not None :
slow = slow.next
fast = fast.next.next
# 反转后半部分
rev = self.reverseList(slow)
# 链表直接对比前后两部分
while rev is not None :
if head.val != rev.val :
return False
head = head.next
rev = rev.next
return True
找到链表中点,并记录前半部分的值,对比中点后链表和前半段记录下的值 (注意链表总数奇偶):此处省略文章来源地址https://www.toymoban.com/news/detail-737989.html
到了这里,关于234. 回文链表、Leetcode的Python实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!