用 Python 检查链表项是否形成回文的程序

pythonserver side programmingprogramming更新于 2026/2/2 9:16:17

假设我们有一个链表。我们必须检查列表元素是否形成回文。因此，如果列表元素为 [5,4,3,4,5]，那么这是一个回文，但像 [5,4,3,2,1] 这样的列表不是回文。

为了解决这个问题，我们将遵循以下步骤 −

fast := head, slow := head, rev := None and flag := 1
如果 head 为空，则返回 true
当 fast 和 fast 的下一个可用时
- 如果 fast 的下一个的下一个可用，则设置 flag := 0 并中断循环
- fast := fast 的下一个的下一个
- temp := slow, slow := slow 的下一个
- temp 的下一个 := rev，并且 rev := temp
fast := slow 的下一个，且 slow 的下一个 := rev
如果设置了标志，则 slow := slow 的下一个
当 fast 和 slow 不为 None 时，
- 如果 fast 的值与 slow 的值不同，则返回 false
- fast := fast 的下一个，且 slow := slow 的下一个
返回 True

让我们看看下面的实现以便更好地理解 −

示例

class ListNode:
   def __init__(self, data, next = None):
      self.data = data
      self.next = next
def make_list(elements):
   head = ListNode(elements[0])
   for element in elements[1:]:
      ptr = head
      while ptr.next:
         ptr = ptr.next
      ptr.next = ListNode(element)
   return head
class Solution(object):
   def isPalindrome(self, head):
      fast,slow = head,head
      rev = None
      flag = 1
      if not head:
         return True
      while fast and fast.next:
         if not fast.next.next:
            flag = 0
            break
      fast = fast.next.next
      temp = slow
      slow = slow.next
      temp.next = rev
      rev = temp
      fast = slow.next
      slow.next = rev
      if flag:
         slow = slow.next
         while fast and slow:
            if fast.data != slow.data:
               return False
      fast = fast.next
      slow = slow.next
      return True
      head = make_list([5,4,3,4,5])
ob1 = Solution()
print(ob1.isPalindrome(head))