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.next:
            fast = fast.next.next
            slow = slow.next

        if fast is None:
            return slow, False
        
        return slow, True
    
    def reverse(self, head):
        result = None
        current = head
        
        while current:
            nextNode = current.next
            
            current.next = 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 = head1.next
            head2 = head2.next
            
        # 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 = mid.next
        
        second = self.reverse(mid)
        
        return self.compareLists(head, second)

Reference

Written with StackEdit.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: