Published: Sep 12, 2022

## Introduction

A brute force solution would be saving values to an array, then compared both start and end. Another solutions is reversing first half and compares the values.

## Problem Description

Given the `head` of a singly linked list, return `true` if it is a palindrome or `false` otherwise.

Constraints:

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

## Examples

``````Example 1:
Output: true
``````
``````Example 2:
Output: false
``````

## Analysis

The solution here reverses the first half of the linked list. It uses three pointers, slow, fast, and reversed. When the fast pointer reaches to the end, the first half is reversed. The slow pointer is on the middle. If the length of the linked list is odd, fast pointer has a next node still. In this case, slow pointer is incremented by one. The comparison ends when revered pointer reaches to the end.

## Solution

``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def isPalindrome(self, head: Optional[ListNode]) -> bool:
while fast and fast.next:
fast = fast.next.next
rev, rev.next, slow = slow, rev, slow.next
if fast:
slow = slow.next
while rev:
if rev.val != slow.val:
return False
rev, slow = rev.next, slow.next
return True
``````

## Complexities

• Time: `O(n)`
• Space: `O(1)`