leetcode_链表 234.回文链表

234.回文链表

• 给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是, 返回 true ; 否则, 返回false。
• 思路：
  1. 找到中间节点(快慢指针法)
  2. 反转后半部分的链表
  3. 比较前半部分和后半部分链表

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def isPalindrome(self, head):""":type head: Optional[ListNode]:rtype: bool"""if not head or not head.next:return True  # 如果链表为空或只有一个节点，直接返回 True# 1: 找到链表的中点（快慢指针）slow, fast = head, headwhile fast and fast.next:slow = slow.nextfast = fast.next.next# 2: 反转后半部分链表prev = Nonewhile slow:next_node = slow.nextslow.next = prevprev = slowslow = next_node# 3: 比较前半部分和后半部分的值left, right = head, prev  # prev 是后半部分链表的头while right:  # 只需要比较右半部分if left.val != right.val:return Falseleft = left.nextright = right.nextreturn True

• 时间复杂度：O(n)，其中 n 是链表的长度，总共遍历了三遍链表，n+n+n = 3n，时间复杂度忽略常数级故为O(n)
• 空间复杂度：O(1)