リンクリスト項目をチェックするプログラムがPythonで回文を形成しているかどうか

リンクリストがあるとします。リスト要素が回文を形成しているかどうかを確認する必要があります。したがって、リスト要素が[5,4,3,4,5]のような場合、これは回文ですが、[5,4,3,2,1]のようなリストは回文ではありません。

これを解決するには、次の手順に従います-

• 高速：=ヘッド、低速：=ヘッド、回転：=なし、フラグ：=1
• ヘッドが空の場合は、trueを返します
• 高速および次の高速が利用可能である間
  • 次の高速が利用可能な場合は、フラグ：=0を設定し、ループを解除します
  • fast：=next of the next of fast
  • temp：=遅い、遅い：=次の遅い
  • temp：=revの次、およびrev：=temp
• fast：=next of slow、next of slow：=rev
• フラグが設定されている場合、slow：=next of slow
• 高速と低速はなしではありませんが、
  • fastの値がslowの値と同じでない場合は、falseを返します
  • fast：=next of fast、slow：=next of 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))

入力

[5,4,3,4,5]

出力

True