回文链表在 Python 中

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

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

  • fast := head, slow := head, rev := None 且 flag := 1

  • 如果 head 为空，则返回 True

  • 当 fast 和 fast 的下一个可用时

    • 如果 fast 的下下一个可用，则设置 flag := 0 并 break 循环

    • fast := fast 的下下一个

    • temp := slow, slow := slow 的下一个

    • temp 的下一个 := rev，且 rev := temp

  • fast := slow 的下一个，且 slow 的下一个 := rev

  • 如果 flag 设置，则 slow := slow 的下一个

  • 当 fast 和 slow 均不为 None 时

    • 如果 fast 的值不与 slow 的值相同，则返回 False

    • fast := fast 的下一个，且 slow := slow 的下一个

  • 返回 True

示例（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

更新日期：2020 年 4 月 27 日

1K+ 浏览数

开启你的 职业生涯

完成课程获得认证

开始
广告