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, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2: 反转后半部分链表
        prev = None
        while slow:
            next_node = slow.next
            slow.next = prev
            prev = slow
            slow = next_node

        # 3: 比较前半部分和后半部分的值
        left, right = head, prev  
        # prev 是后半部分链表的头
        while right:  
        # 只需要比较右半部分
            if left.val != right.val:
                return False
            left = left.next
            right = right.next

        return True

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