【Leetcode刷题Python】234.回文链表

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