一、题目描述：
给定一个链表，请判断该链表是否为回文结构。
示例1
输入：[1]
返回值：true
示例2
输入：[2,1]
返回值：false
说明：2->1
示例3
输入：[1,2,2,1]
返回值：true
说明：1->2->2->1
二、解题思路及代码：
（一）利用栈的特性,利用数组存储值进行判断
因为如果链表是回文的，那么将整个链表反转后肯定还是跟原链表是一样的。所以我们就利用栈的先进后出的特性，将整个链表的节点放进栈中，然后进行出栈操作相当于链表反转的作用，再进行依次遍历比较。
class Solution:
def isPail(self , head ):
# write code here
#节点值比较方法
if not head:
return True
stack = []
cur = head
while cur:
stack.append(cur.val)
cur = cur.next
return stack == stack[::-1]
复杂度分析：
时间复杂度：O(n), 循环遍历次数取决于链表的长度。
空间复杂度：O(n),使用了栈，空间大小取决于链表的长度。
（二）利用快慢指针找到中点，分割成两条链，在进行值判断
即分为三个步骤:找中点+反转链表+遍历比较
1、快慢指针找中点 先使用快慢指针找到链表的中点，然后根据中点找到表示后半段链表的头节点。
可以利用快慢指针，快指针一次走两步，慢指针依次走一步，当快指针走到终点的时候，此时如果链表的长度为偶数时，此时中间节点有两个，慢指针则走到了左端点。反之，慢指针则走到中间节点。（第二个链表的长度比第一个链表的长度小1）
2、反转链表
具体已记录在:: 反转链表【刷题记录】.
3、遍历比较
class Solution:
def isPail(self , head ):
# write code here
if head == None or head.next == None:
return True
slow = head
fast = head
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
##从中点断开 分成两条链 head and slow
pre.next = None
## 链表反转
head2 = None
while slow:
temp = slow.next
slow.next = head2
head2 = slow
slow = temp
while head and head2:
if head.val != head2.val:
return False
head = head.next
head2 = head2.next
return True
复杂度分析：
时间复杂度：O(n), 循环遍历次数。
空间复杂度：O(1), 没有使用额外的空间。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/99769.html
