假设我们有一个链表。我们必须检查列表元素是否正在形成回文。因此,如果列表元素类似于[1,2,3,2,1],则这是回文。
为了解决这个问题,我们将遵循以下步骤-
快:=头,慢:=头,转速:=无和标志:= 1
如果头部为空,则返回true
快而快的时候可用
如果快速下一个的下一个可用,则设置标志:= 0并中断循环
快速:=快速的下一个
temp:=慢,慢:=下一个慢
temp的下一个:= rev和rev:= temp
快:=慢速下一个,慢速下一个:=转
如果设置了标志,则慢速:=慢速的下一个
虽然快和慢不是没有,
如果fast的值与lower的值不同,则返回false
快速:=快速的下一个,慢速:=慢速的下一个
返回真
让我们看下面的实现以更好地理解-
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