Published: Sep 12, 2022
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.
headof a singly linked list, return
trueif it is a palindrome or
- The number of nodes in the list is in the range
0 <= Node.val <= 9
Example 1: Input: head = [1,2,2,1] Output: true
Example 2: Input: head = [1,2] Output: false
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.
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class PalindromeLinkedList: def isPalindrome(self, head: Optional[ListNode]) -> bool: fast, slow, rev = head, head, None 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