[Solved] Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Question

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

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?

Python 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: ListNode) -> bool:
        l = 0
        p = head
        
        while p:
            l+=1
            p=p.next
        
        prev = None
        curr = head
        for _ in range(l//2):
            nex = curr.next
            curr.next = prev
            prev = curr 
            curr = nex
        
        if l%2==1:
            curr = curr.next
        
        while curr:
            if curr.val!=prev.val:
                return False
            curr = curr.next
            prev = prev.next
        
        return True