I am trying to solve LeetCode problem 234. Palindrome Linked List
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
My code worked for lists with an even amount of nodes. When I tried to change it with an if statement to advance one more node, the code started to loop. The code prints 'here' at the bottom but does not return True and instead loops and runs again.
There is an error with the tail.next = None line when it runs a second time.
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return True
slow = fast = prev = head
count = 0
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
count += 1
if count % 2 == 1:
prev = slow
slow = slow.next
curr = slow
tail = curr
start = prev
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
tail.next = None
start.next = prev
slow = fast = head
for x in range(count):
fast = fast.next
while fast:
if slow.val != fast.val:
return False
slow = slow.next
fast = fast.next
print('here')
return True
There are several issues:
if count % 2 == 1: makes no sense. We can imagine there is a slight difference between a list with an even number of nodes and one with an odd number of nodes, but count does not represent the number of nodes in the list: it represents half the number of nodes in the list. And whether that count is odd or even has no relevant meaning.
Related to the previous point, if the list has two nodes, then count will be one, and so you'll set slow to None by this if block. This will result in an exception when executing tail.next = None as tail is None at that moment.
start.next = prev is a dangerous assignment. If the preceding while loop only makes one iteration, then start == prev and this assignment will create a loop. This happens if the previous point is resolved by removing tail.next = None to avoid the exception, and the input is a list with two nodes. The program will get into an infinite loop.
Some other remarks:
It should not be necessary to keep a count. As explained above, it serves no purpose when wanting to know the parity of the list. And the loop that you have near the end, that is based on count, can be replaced by fast = prev, as just had just reversed the second half, and made prev the head of that second list.
You wrote "The code prints 'here' at the bottom but does not return True and instead loops and runs again.". This is a misunderstanding. It does return, but LeetCode continues to run a second test case.
Here is a fix of your code:
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return True
# Find center: no need for a counter
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev = None # This is the way to ensure the reversed list ends with None
while slow:
next_node = slow.next
slow.next = prev
prev = slow
slow = next_node
# Compare halves, we can reuse `head`
fast = prev # No loop needed, we know where the second half starts
while fast:
if head.val != fast.val:
return False
head = head.next
fast = fast.next
return True