is_palindrome.py

from __future__ importannotations

fromdataclassesimportdataclass


@dataclass
classListNode:
val: int=0
next_node: ListNode|None=None


defis_palindrome(head: ListNode|None) ->bool:
"""
 Check if a linked list is a palindrome.

 Args:
 head: The head of the linked list.

 Returns:
 bool: True if the linked list is a palindrome, False otherwise.

 Examples:
 >>> is_palindrome(None)
 True

 >>> is_palindrome(ListNode(1))
 True

 >>> is_palindrome(ListNode(1, ListNode(2)))
 False

 >>> is_palindrome(ListNode(1, ListNode(2, ListNode(1))))
 True

 >>> is_palindrome(ListNode(1, ListNode(2, ListNode(2, ListNode(1)))))
 True
 """
ifnothead:
returnTrue
# split the list to two parts
fast: ListNode|None=head.next_node
slow: ListNode|None=head
whilefastandfast.next_node:
fast=fast.next_node.next_node
slow=slow.next_nodeifslowelseNone
ifslow:
# slow will always be defined,
# adding this check to resolve mypy static check
second=slow.next_node
slow.next_node=None# Don't forget here! But forget still works!
# reverse the second part
node: ListNode|None=None
whilesecond:
nxt=second.next_node
second.next_node=node
node=second
second=nxt
# compare two parts
# second part has the same or one less node
whilenodeandhead:
ifnode.val!=head.val:
returnFalse
node=node.next_node
head=head.next_node
returnTrue


defis_palindrome_stack(head: ListNode|None) ->bool:
"""
 Check if a linked list is a palindrome using a stack.

 Args:
 head (ListNode): The head of the linked list.

 Returns:
 bool: True if the linked list is a palindrome, False otherwise.

 Examples:
 >>> is_palindrome_stack(None)
 True

 >>> is_palindrome_stack(ListNode(1))
 True

 >>> is_palindrome_stack(ListNode(1, ListNode(2)))
 False

 >>> is_palindrome_stack(ListNode(1, ListNode(2, ListNode(1))))
 True

 >>> is_palindrome_stack(ListNode(1, ListNode(2, ListNode(2, ListNode(1)))))
 True
 """
ifnotheadornothead.next_node:
returnTrue

# 1. Get the midpoint (slow)
slow: ListNode|None=head
fast: ListNode|None=head
whilefastandfast.next_node:
fast=fast.next_node.next_node
slow=slow.next_nodeifslowelseNone

# slow will always be defined,
# adding this check to resolve mypy static check
ifslow:
stack= [slow.val]

# 2. Push the second half into the stack
whileslow.next_node:
slow=slow.next_node
stack.append(slow.val)

# 3. Comparison
cur: ListNode|None=head
whilestackandcur:
ifstack.pop() !=cur.val:
returnFalse
cur=cur.next_node

returnTrue


defis_palindrome_dict(head: ListNode|None) ->bool:
"""
 Check if a linked list is a palindrome using a dictionary.

 Args:
 head (ListNode): The head of the linked list.

 Returns:
 bool: True if the linked list is a palindrome, False otherwise.

 Examples:
 >>> is_palindrome_dict(None)
 True

 >>> is_palindrome_dict(ListNode(1))
 True

 >>> is_palindrome_dict(ListNode(1, ListNode(2)))
 False

 >>> is_palindrome_dict(ListNode(1, ListNode(2, ListNode(1))))
 True

 >>> is_palindrome_dict(ListNode(1, ListNode(2, ListNode(2, ListNode(1)))))
 True

 >>> is_palindrome_dict(
 ... ListNode(
 ... 1, ListNode(2, ListNode(1, ListNode(3, ListNode(2, ListNode(1)))))
 ... )
 ... )
 False
 """
ifnotheadornothead.next_node:
returnTrue
d: dict[int, list[int]] = {}
pos=0
whilehead:
ifhead.valind:
d[head.val].append(pos)
else:
d[head.val] = [pos]
head=head.next_node
pos+=1
checksum=pos-1
middle=0
forvind.values():
iflen(v) %2!=0:
middle+=1
else:
forstep, iinenumerate(range(len(v))):
ifv[i] +v[len(v) -1-step] !=checksum:
returnFalse
ifmiddle>1:
returnFalse
returnTrue


if__name__=="__main__":
importdoctest

doctest.testmod()