Traverse the linked list and store all node values in an array. Then use two pointers from the start and end of the array, comparing values moving inward. If all pairs match, the list is a palindrome.
Use the fast and slow pointer technique to find the middle of the linked list. Reverse the second half in-place, then compare nodes from the start and the reversed second half one by one.
""" 0234.1 - Palindrome Linked List - Solution 1 - Convert to Array """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional, List
#####################################################################################
# Classes
#####################################################################################
class ListNode:
"""ListNode Class"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""Solution Class"""
def isPalindrome(self, head: Optional[ListNode]) -> bool:
"""Palindrome Linked List Function"""
vals = []
curr = head
while curr:
vals.append(curr.val)
curr = curr.next
left, right = 0, len(vals) - 1
while left < right:
if vals[left] != vals[right]:
return False
left += 1
right -= 1
return True
#####################################################################################
# Functions
#####################################################################################
def build_list(arr: List[int]) -> Optional[ListNode]:
"""Helper to build linked list from array"""
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def testcase():
"""Test Function"""
print(Solution().isPalindrome(build_list([1, 2, 2, 1]))) # True
print(Solution().isPalindrome(build_list([1, 2]))) # False
print(Solution().isPalindrome(build_list([1]))) # True
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0234.2 - Palindrome Linked List - Solution 2 - Reverse Second Half In-Place """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional, List
#####################################################################################
# Classes
#####################################################################################
class ListNode:
"""ListNode Class"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""Solution Class"""
def isPalindrome(self, head: Optional[ListNode]) -> bool:
"""Palindrome Linked List Function"""
# Find the middle using slow and fast pointers
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse the second half
prev = None
while slow:
nxt = slow.next
slow.next = prev
prev = slow
slow = nxt
# Compare first half and reversed second half
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
#####################################################################################
# Functions
#####################################################################################
def build_list(arr: List[int]) -> Optional[ListNode]:
"""Helper to build linked list from array"""
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def testcase():
"""Test Function"""
print(Solution().isPalindrome(build_list([1, 2, 2, 1]))) # True
print(Solution().isPalindrome(build_list([1, 2]))) # False
print(Solution().isPalindrome(build_list([1]))) # True
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()