# Definition for singly-linked list.

# class ListNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution(object):

    def isPalindrome(self, head):

        """

        :type head: ListNode

        :rtype: bool

        """

        total = 0

        p1 = p2 = head

        while p1:

            total += 1

            p1 = p1.next

        if total < 2:

            return True

        half = total // 2 - 1

        while half :

            p2 = p2.next

            half -= 1

        if total % 2 == 1:

            part_2 = p2.next.next

        else:

            part_2 = p2.next

        p2.next , last = None , None

        while part_2:

            new_head = part_2.next

            part_2.next = last

            last = part_2

            part_2 = new_head

        while head:

            if not last or head.val != last.val:

                return False

            head , last= head.next , last.next

        return True
        

class Solution:

    def isPalindrome(self, head: ListNode) -> bool:

        if not head or not head.next:

            return True

        new_list = []

        # 快慢指针法找链表的中点

        slow = fast = head

        while fast and fast.next:

            new_list.insert(0, slow.val)

            slow = slow.next

            fast = fast.next.next

        if fast: # 链表有奇数个节点

            slow = slow.next

        for val in new_list:

            if val != slow.val:

                return False

            slow = slow.next

        return True

# Definition for singly-linked list.

# class ListNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution(object):

    def isPalindrome(self, head):

        """

        :type head: ListNode

        :rtype: bool

        """

        if not head or not head.next:

            return True

        # 快慢指针法找链表的中点

        slow = fast = head

        while fast.next and fast.next.next:

            slow = slow.next

            fast = fast.next.next

        slow = slow.next # slow指向链表的后半段

        slow = self.reverseList(slow)

        while slow:

            if head.val != slow.val:

                return False

            slow = slow.next

            head = head.next

        return True

    def reverseList(self, head):

        new_head = None

        while head:

            p = head

            head = head.next

            p.next = new_head

            new_head = p

        return new_head