LeetCode: 234. Palindrome Linked List

Solution for Q.234 within O(N) time complexity and O(1) memory.

To check whether it's a palindrome, we have to check two elements simultaneously from the head and tail.

But in singly linked list, we have no way to check the elements in reverse order from the tail.

So, the solution is simple. Reverse the second half of the list and compare two lists.

Below is the code.

# 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: Optional[ListNode]) -> bool:
        if not head.next:
            return True
        fast, slow = head, head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
        
        cur, prv = slow, None
        while cur:
            nxt = cur.next
            cur.next = prv
            prv = cur
            cur = nxt
        
        p1 = head 
        p2 = prv
        if fast == None:
            while p2:
                if p2.val != p1.val:
                    return False
                p1 = p1.next
                p2 = p2.next
            return True
        else:
            while p2.next:
                if p2.val != p1.val:
                    return False
                p1 = p1.next
                p2 = p2.next
            return True