Python程式檢查連結串列元素是否構成迴文

假設我們有一個連結串列。我們需要檢查連結串列元素是否構成迴文。例如，列表元素為[5,4,3,4,5]，則為迴文；而列表元素為[5,4,3,2,1]則不是迴文。

為了解決這個問題，我們將遵循以下步驟：

  • fast := head，slow := head，rev := None，flag := 1
  • 如果head為空，則返回true
  • 當fast及其下一個節點存在時
    • 如果fast的下一個節點的下一個節點存在，則設定flag := 0並中斷迴圈
    • fast := fast的下一個節點的下一個節點
    • temp := slow，slow := slow的下一個節點
    • temp的下一個節點 := rev，rev := temp
  • fast := slow的下一個節點，slow的下一個節點 := rev
  • 如果flag已設定，則slow := slow的下一個節點
  • 當fast和slow都不為空時
    • 如果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))

輸入

[5,4,3,4,5]

輸出

True

更新於：2020年10月20日

瀏覽量：103

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告