回文

定位回文问题，首先找到中点，在中点可以将链表分为两部分。 然后将前段或者后段链表使用头插法倒序，可进行比较。

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        #判断是否为空
        if head == None:
            return True
        
        #将slow指向后半段起始节点
        slow = head 
        fast = head.next
        while fast != None and fast.next != None:
            slow = slow.next
            fast = fast.next.next
        if fast != None:
            slow = slow.next

		#将后半段逆序
        slownew = slow
        while slow.next != None:
            tmp = slow.next
            slow.next = tmp.next
            tmp.next = slownew
            slownew = tmp
        
        #前后半段比较
        while slownew != None:
            if slownew.val != head.val:
                return False
            slownew = slownew.next 
            head = head.next
        return True

链表O(n)操作技巧

快慢指针

快慢指针可以找到链表中点

头插法

用头插法可将链表倒序