題目

請(qǐng)判斷一個(gè)鏈表是否為回文鏈表。
示例 1:
輸入: 1->2
輸出: false

示例 2:
輸入: 1->2->2->1
輸出: true
進(jìn)階：
你能否用 O(n) 時(shí)間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題？

思路

1. 利用雙指針找到鏈表的中間位置
   每一次慢指針移動(dòng)一步，快指針移動(dòng)兩步，當(dāng)快指針遍歷到鏈表最后的時(shí)候，慢指針正好指向鏈表中間節(jié)點(diǎn)
2. 將后半部分鏈表反轉(zhuǎn)
3. 反轉(zhuǎn)后，遍歷比較前半段和后半段鏈表，主要終止條件

代碼

class Solution(object):
    def isPalindrome(self, head):
        if head == None or head.next == None:
            return True
        slow = head
        fast = head
        while fast and fast.next: # 注意終止條件
            slow = slow.next
            fast = fast.next.next

        mid = slow # 找到鏈表的中間節(jié)點(diǎn)
        new_head = None
        while mid: # 將后半段鏈表反轉(zhuǎn)
            nxt = mid.next
            mid.next = new_head
            new_head.next = mid
            mid = nxt

        while head != slow: # 判斷是否是回文表
            if head.val == new_head.val:
                head = head.next
                new_head = new_head.next
            else:
                return False
        return True