leetcode_234. 回文链表

举报
悲恋花丶无心之人 发表于 2021/02/03 02:23:32 2021/02/03
【摘要】 目录 一、题目内容 二、解题思路 三、代码 一、题目内容 请判断一个链表是否为回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题? 二...

目录

一、题目内容

二、解题思路

三、代码


一、题目内容

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

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

二、解题思路

先用一个list存储每个节点的值,然后首尾双指针前后移动判断每个对称位置的元素值是否相等即可。

三、代码


  
  1. # Definition for singly-linked list.
  2. class ListNode:
  3. def __init__(self, x):
  4. self.val = x
  5. self.next = None
  6. def __repr__(self):
  7. return str(self.val)
  8. class Solution:
  9. def isPalindrome(self, head: ListNode) -> bool:
  10. p = head
  11. cache = []
  12. while p:
  13. cache.append(p.val)
  14. p = p.next
  15. i = 0
  16. j = len(cache) - 1
  17. while i <= j:
  18. if cache[i] == cache[j]:
  19. i += 1
  20. j -= 1
  21. else:
  22. return False
  23. return True
  24. if __name__ == '__main__':
  25. a = ListNode(1)
  26. a.next = ListNode(2)
  27. a.next.next = ListNode(2)
  28. a.next.next.next = ListNode(1)
  29. s = Solution()
  30. ans = s.isPalindrome(a)
  31. print(ans)

文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。

原文链接:nickhuang1996.blog.csdn.net/article/details/109236973

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。