https://leetcode.com/problems/palindrome-linked-list

If we want to get O(n) time and O(1) space complexity, we need to do in in long way:

  1. Find middle of our list, we can do it with two pointers approach: one moving with speed 1 and another with speed 2 (or alternatively we can just evaluate length and then find middle). At the end of this step slow pointer will point to the end of first half.
  2. We need to reverse the second half of our linked list. For this we will use Problem 206. Reverse Linked List, the idea is to again use two pointers.
  3. Traverse in parallel first half and second half and compare element by element. If we have different element, we mark found = True. We do not return result immedietly, because we changed our list and we want to change it back.
  4. Reverse back second half of the list, and attach it back to the end of first half.

Complexity

Time complexity is just O(n), however with constant around 5, because we traverse likst several times and inside each traversal we do several operations. This is the reason, why it will not be the fastest solution. Space complexity is just O(1), because we reattach already existing nodes.

Code

class Solution:
    def isPalindrome(self, head):
        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

If you like the solution, you can upvote it on leetcode discussion section: Problem 0234