题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

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

输出：head = [1,2,2,1]输入：true输出：head = [1,2]输入：false

思路

第一个想到的就是，间接把整个链表翻转，而后和原来的链表比拟。
然而题目要求工夫复杂度O(n)，空间复杂度O(1)，这个思路要保留翻转后的链表，空间复杂度首先就不满足了。

满足复杂度的思路如下：

1. 将链表从两头一分为二
   应用快慢指针，slow每次挪动1个节点，fast每次挪动2个节点。当fast挪动到开端，无奈继续前进2个节点时，slow所在的节点就是链表的两头地位。
2. 将右半局部链表翻转
3. 遍历左、右两个链表的每个节点，看每个节点的值是否雷同

def isPalindrome(self, head: ListNode) -> bool:        # 初始化快慢指针        slow = fast = head        # 遍历链表，挪动快慢指针，切分链表        # 当fast挪动到尾节点或尾节点的前一个节点时，下一次无奈挪动2个节点，则遍历实现        # 此时slow指针指向了链表的两头地位        while fast.next and fast.next.next:            slow = slow.next            fast = fast.next.next        # 翻转右半局部链表        # 在翻转后的右半局部链表头节点设置rightHead指针        rightHead = self.reverseList(slow.next)        # 在左半局部链表头节点设置leftHead指针        leftHead = head        # 以遍历右半局部链表为准，因为切分链表的时候，如果链表节点个数是奇数，左半局部会多1个节点        while rightHead:            # 如果有节点的值不同，就不是回文链表，返回False            if leftHead.val != rightHead.val:                return False            # 挪动指针            leftHead = leftHead.next            rightHead = rightHead.next                    # 遍历完结，节点的值都雷同，是回文链表，返回True        return True            def reverseList(self,head):        if head==None or head.next==None:            return head        tmp = self.reverseList(head.next)        head.next.next = head        head.next = None        return tmp