Palindrome Linked List

基本思路还是只能利用快慢指针反转前半或者后半部分链表再逐个比对，这道题是比较少见的有dummy node逻辑不好看的题目了

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        if fast:
            slow = slow.next
        slow = self.reverse(slow)
        fast = head
        while slow:
            if slow.val != fast.val:
                return False
            slow = slow.next
            fast = fast.next

        return True    

    def reverse(self, root):
        pre, nxt = None, None
        while root:
            nxt = root.next
            root.next = pre
            pre = root
            root = nxt
        return pre