CODEWITHSUNDEEP
pythonalgorithmlinked-listpalindrome
GilbertLee
GilbertLee

Reputation: 696

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

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.

Upvotes: 2

Views: 4687

Answers (2)

Yilmaz
Yilmaz

Reputation: 49190

I commented key points on the solution:

class Solution:
    def with_array(self,head:ListNode)->bool:
        # this makes S:O(N)
        nums=[]
        while head:
            nums.append(head.val)
            head=head.next
        l,r=0,len(nums)-1
        while l<=r:
            if nums[l]!=nums[r]:
                return False
            l+=1
            r-=1
        return True

    def optimum(self,head:ListNode)->bool:
        fast_pointer=head
        slow_pointer=head
        # I wanna reach the end of the linked list. I stop when fast_pointer.next=None
        while fast_pointer and fast_pointer.next:
            # we are forwarding fast_pointer twice
            fast_pointer=fast_pointer.next.next
            # while slow reach middle, fast will reach to the end
            slow_pointer=slow_pointer.next
            # at the end of this while loop, slow_pointer will be in middle, fast_pointer will be at the end
        
        # reverse the second half of the list, from slow_pointer till the fast_pointer
        # at the end of the reverse, prev will point to the last node 
        prev=None
        while slow_pointer:
            temp=slow_pointer.next
            slow_pointer.next=prev
            # eventually prev will point to the last node
            prev=slow_pointer
            slow_pointer=temp
        # check if it is a palindrome
        # remember, after reversing, prev=tail
        left,right=head,prev
        while right:
            if left.val!=right.val:
                return False
            left=left.next
            right=right.next
        return True

Upvotes: 0

Sven Marnach
Sven Marnach

Reputation: 601529

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.

Upvotes: 14

Related Questions