請判斷一個鏈表是否為迴文鏈表。 示例 1: 輸入: 1->2 輸出: false 示例 2: 輸入: 1->2->2->1 輸出: true 進階: 你能否用 O(n) 時間複雜度和 O(1) 空間複雜度解決此題? # Definition for singly-linked list. # cla ...
請判斷一個鏈表是否為迴文鏈表。
示例 1:
輸入: 1->2 輸出: false
示例 2:
輸入: 1->2->2->1 輸出: true
進階:
你能否用 O(n) 時間複雜度和 O(1) 空間複雜度解決此題?
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverst(self,head): a=head b=head.next head.next = None; while b: c = b.next b.next = a a = b b=c head = a return head def isPalindrome(self, head): """ :type head: ListNode :rtype: bool """ if not head or not head.next: return True fast = slow = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next slow = slow.next slow = self.reverst(slow) while slow: if head.val != slow.val: return False slow = slow.next head = head.next return True