题目描述

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

示例 1:

输入: 1->2
输出: false

示例 2:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if head is None or head.next is None :return True
        # 反转链表 同时计数
        pre=ListNode(head.val) 
        print(pre.val)
        pre.next = None
        cur = head.next
        
        long = 1
        # print(cur)
        while cur :
            long += 1
            temp = cur.next
            phead = ListNode(cur.val)
            phead.next = pre
            pre = phead
            cur = temp

        k = (long+1)/2 
        while pre is not None and head is not None and k >= 0:
            print(pre.val,"---",head.val)
            if pre.val != head.val:
                print(pre.val,"---",head.val)
                return False
            pre = pre.next
            head = head.next
            k -= 1
        return True

总结

链表反转