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
