Palindrome Linked List in Python with O(1) Extra Space

Question

This is the #234 Leetcode problem:

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

This problem is easy to solve with O(n) space. However, I cannot figure out the O(1) solution. The only way I think of is to use recursion:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    current = None

    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return True

        self.current = head

        return self.compare(head)

    def compare(self, head):
        if not head: return True

        if not self.compare(head.next): return False

        if head.val != self.current.val:
            return False
        else:
            self.current = self.current.next
            return True

This works with small samples but gives

maximum recursion depth exceeded

Anyone can provide a solution using only O(1) space? Thank you.

Answer 1

If you are allowed to modify the list in place, you can do the following:

1. Iterate over the list to count how many elements there are.
2. Iterate a second time, and starting from the middle of the list, reverse the pointers in the list nodes so that they point to the previous node rather than the next. Remember the last node.
3. Now you have a pointer to the first node and the last node, and can iterate towards the middle from either end, until you either find a difference (no palindrome) or reach the middle (palindrome).
4. Reverse the pointers in the second half to bring them back to their original state.

This will only require constant additional space, and has linear execution time.