Problem statement

https://binarysearch.com/problems/Palindrome-Linked-List/

Solution

Equal to Leetcode 0234. Palindrome Linked List.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def solve(self, head):
        if not head: return True
        def reverse(head):
            curr = None
            nxt = head
            while nxt:
                tmp = nxt.next
                nxt.next = curr
                curr = nxt
                nxt = tmp
            return curr
        
        fast, slow = head, head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
            
        half1, half2 = head, reverse(slow.next)
        save = half2
        found = False
        
        while half1 and half2:
            if half1.val != half2.val:
                found = True
                break
            half1 = half1.next
            half2 = half2.next
            
        slow.next = reverse(save)
        return not found