现给定一个链表ListNode* pHead,定义bool代表链表是否为回文,请编写程序。
测试样例:
{1,2,3,2,1}
返回:true
{1,2,3,2,3}
返回:false
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Palindrome: def isPalindrome(self, pHead): # write code here p = pHead flag = False valList = [] while p != None: valList.append(p.val) p = p.next for i in range(0,len(valList)): if valList[i] == valList[0-(i+1)]: flag = True else: flag = False break return flag
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Palindrome: def isPalindrome(self, pHead): if not pHead or not pHead.next: return False stack = [] slow = pHead fast = pHead.next stack.append(slow.val) while True: # 链表是偶数长度 if not fast.next: mid = slow.next break elif fast.next and not fast.next.next: mid = slow.next.next break slow = slow.next fast = fast.next.next stack.append(slow.val) while stack and mid: top = stack.pop() if top != mid.val: return False mid = mid.next return True