Leetcode: Palindrome Linked List

Palindrome Linked List | LeetCode OJ

There are multiple ways to solve this,

1. Store values in an array, check if array is a pallindrome
2. Store values in a stack, compare values in stack to values in given list

The methods listed above require storing the values and therefore take O(n) space. We can do this without storing the values in the following way

1. Iterate to the middle of the list while reversing it
2. To find the middle, take 2 pointers slow and fast such that slow moves 1 node and fast moves 2 nodes till fast reaches the end
3. Skip the middle element in case of odd sized list
4. Move forward with one pointer and backward with the reversed head while comparing the values

Although this approach answers the question but it is not desirable to modify the input. We can correct it by reversing the list again while traversing backwards.

Remarks:

1. O(1) space complexity, only 4 pointers used
2. O(n) time complexity, traversing first half of linked list twice and the second half once i.e. O(3/2*n)

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return True
        p, q, r, s = None, head, head.next, head
        while s and s.next:
            s = s.next.next
            q.next = p
            p = q
            q = r
            r = r.next
        if s:
            q = q.next
        while p:
            if p.val != q.val:
                return False
            p = p.next
            q = q.next
        return True