Palindrome Linked Lists O(1) Space Solution

There are three isolated steps:

  1. Find the mid of the list
  2. Reverse half of the list and create a new head
  3. Compare two heads
class Solution(object):
    def findMiddle(self, head):
        slow = fast = head
        # find the mid node
        while fast and
            fast =
            slow =

        if fast is None:
            return slow, False
        return slow, True
    def reverse(self, head):
        result = None
        current = head
        while current:
            nextNode =
   = result
            result = current
            current = nextNode
        return result
    def compareLists(self, head1, head2):
        # print("comparing head1={} head2={}".format(head1, head2))
        if head1 is None and head2 is None:
            return True
        while head1 and head2:
            if head1.val != head2.val:
                # print("lists are not same")    
                return False
            head1 =
            head2 =
        # print("lists are same")    
        return True
    def isPalindrome(self, head):
        :type head: ListNode
        :rtype: bool
        mid, odd = self.findMiddle(head)
        # reverse the second half
        if odd:
            mid =
        second = self.reverse(mid)
        return self.compareLists(head, second)


Written with StackEdit.

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: