LeetCode热题100-回文链表

给你一个单链表的头节点head请你判断该链表是否为回文链表。如果是返回true否则返回false。示例 1输入head [1,2,2,1]输出true思路一记录所有值到列表中然后判断这些值是否为回文数。时间复杂度On空间复杂度On.class Solution: def isPalindrome(self, head: Optional[ListNode]) - bool: arr [] cur head while cur: arr.append(cur.val) cur cur.next return arr arr[::-1]思路二空间复杂度O1快慢指针找到链表中点反转后半段链表前后两段逐一比# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def isPalindrome(self, head: Optional[ListNode]) - bool: if not head or not head.next: return True # 先找到中点 slow fast head while fast and fast.next: slow slow.next fast fast.next.next def reverse(node): pre None while node: tmp node.next node.next pre pre node node tmp return pre second reverse(slow) # 前后半段逐一对比 p1, p2 head, second while p2: if p1.val ! p2.val: return False p1 p1.next p2 p2.next return True