Python O(n) time and O(1) space

  • 6

    The idea is simple. Reverse the first half of the linked list and compare it to the second half.

    def isPalindrome(self, head):
        count = 0
        node = head
        while node:
            node =
            count += 1
        node = head
        pre = None
        for i in range(count // 2):
            temp =
   = pre
            pre = node
            node = temp
        if count % 2 == 0:
            h2 = node
            h2 =
        h1 = pre
        while h1:
            if h1.val == h2.val:
                h1 =
                h2 =
                return False
        return True

  • 1

    I have the same idea as yours but I reverse the second half. I think it is ok but you did change the structure of the linked list after checking whether it is palindrome. You can just check the linked list and not change it! here is my code.

    def reverseLinkedList(self, head, tail):
    	if head is None or tail is None: return head 
    	if head is tail: return head
    	p1, p2 = head,
    	while p2 is not tail:
    		tmp = = p1
    		p1 = p2
    		p2 = tmp = p1 = None
    	return tail 
    # @param {ListNode} head
    # @return {boolean}
    def isPalindrome(self, head):
    	if head is None or is None: return True
    	p1, p2, even = head, head, False
    		p1 =
    		p2 =
    		if p2 = 
    		else: even = True
    	if head.val != p2.val: return False
    	halfMark = p1
    	if even: halfTail = p1
    	else: halfTail =
    	lastHalf = self.reverseLinkedList(halfTail, p2)
    	checkPos1, checkPos2, result = head, lastHalf, True
    	while result and checkPos1 is not halfMark: 
    		if checkPos1.val != checkPos2.val:
    			result = False
    		checkPos1 = 
    		checkPos2 =
    	self.reverseLinkedList(lastHalf, halfTail)
    	return result

Log in to reply

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