leetcode [234] 回文链表

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

翻转前半个链表。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if head is None:
            return True
        count = 0
        head_ = head
        while head_:
            head_ = head_.next
            count += 1
        mid = count // 2
        pre, cur, post = None, head, head.next
        while cur and mid > 0:
            cur.next = pre
            pre, cur, post = cur, post, post.next if post else None
            mid -= 1
        if count % 2 != 0:
            cur = cur.next
        while pre and cur and pre.val == cur.val:
            pre = pre.next
            cur = cur.next
        if pre == cur == None:
            return True
        return False