234. Palindrome Linked List

234. Palindrome Linked List (Easy) 回文链表

题干

Given the head of a singly linked list, return true if it is a palindrome

or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

解法

快慢指针解法

使用快慢指针，一快一慢，当快指针无法继续前进的时候，慢指针正好是中间节点。

反转后半段的链表，和前半段链表一起循环对比，当节点的value相等时，返回真，任意一个节点的value不相等时，返回假。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 节点范围是[1, 10^5]
        if head.next is None:
            return True
        
        first_half_end_node: ListNode = self.get_first_half_node(head)
        second_half_head: ListNode = self.reverse_list(None, first_half_end_node.next)

        left = head
        right = second_half_head

        while right is not None:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True
    
    def get_first_half_node(self, head: Optional[ListNode]) -> ListNode:
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow
    
    def reverse_list(self, pre: Optional[ListNode], cur: Optional[ListNode]) -> ListNode:
        if cur is None:
            return pre
        temp = cur.next
        cur.next = pre
        return self.reverse_list(cur, temp)