Python solution with bad run time revesed the second half of the list and then back again


  • 0
    H
        # Definition for singly-linked list.
        # class ListNode:
        #     def __init__(self, x):
        #         self.val = x
        #         self.next = None
        
        class Solution:
            # @param {ListNode} head
            # @return {boolean}
            def isPalindrome(self, head):
                if head==None:
                    return True
                if head.next==None:
                    return True
                tail=head
                size=1
                while tail.next!=None:
                    tail=tail.next
                    size+=1
                mid=head
                for i in xrange((size-1)/2):
                    mid=mid.next
                temp=mid
                mid=mid.next
                temp.next=None
                tail=temp
                
                curr=mid
                prev=None
                while curr!=None:
                    temp=curr.next
                    curr.next=prev
                    prev=curr
                    curr=temp
                mid=prev
                curr1=head
                curr2=mid
                res=True
                while curr2!=None:
                    if curr1.val!=curr2.val:
                        res=False
                        break
                    curr1=curr1.next
                    curr2=curr2.next
                curr=mid
                prev=None
                while curr!=None:
                    temp=curr.next
                    curr.next=prev
                    prev=curr
                    curr=temp
                mid=prev
                tail.next=mid
                return res

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.