Python中的回文链接列表

假设我们有一个链表。我们必须检查列表元素是否正在形成回文。因此,如果列表元素类似于[1,2,3,2,1],则这是回文。

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

  • 快:=头,慢:=头,转速:=无和标志:= 1

  • 如果头部为空,则返回true

  • 快而快的时候可用

    • 如果快速下一个的下一个可用,则设置标志:= 0并中断循环

    • 快速:=快速的下一个

    • temp:=慢,慢:=下一个慢

    • temp的下一个:= rev和rev:= temp

  • 快:=慢速下一个,慢速下一个:=转

  • 如果设置了标志,则慢速:=慢速的下一个

  • 虽然快和慢不是没有,

    • 如果fast的值与lower的值不同,则返回false

    • 快速:=快速的下一个,慢速:=慢速的下一个

  • 返回真

范例(Python)

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

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
      #print(fast.val)
      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([1,2,3,2,1])
ob1 = Solution()print(ob1.isPalindrome(head))

输入值

[1,2,3,2,1]

输出结果

True