LeetCode-in-All
234. Palindrome Linked List
Easy
Given the head of a singly linked list, return true if it is a palindrome.
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?
Solution
# 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:
# Calculate the length of the linked list
length = 0
right = head
while right:
right = right.next
length += 1
# Reverse the right half of the list
length //= 2
right = head
for _ in range(length):
right = right.next
prev = None
while right:
next_node = right.next
right.next = prev
prev = right
right = next_node
# Compare the left half and the right half
for _ in range(length):
if head and prev and head.val == prev.val:
head = head.next
prev = prev.next
else:
return False
return True