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


  • 6
    S

    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 = node.next
            count += 1
        node = head
        pre = None
        for i in range(count // 2):
            temp = node.next
            node.next = pre
            pre = node
            node = temp
        if count % 2 == 0:
            h2 = node
        else:
            h2 = node.next
        h1 = pre
        while h1:
            if h1.val == h2.val:
                h1 = h1.next
                h2 = h2.next
            else:
                return False
        return True

  • 1
    C

    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, head.next
    	while p2 is not tail:
    		tmp = p2.next
    		p2.next = p1
    		p1 = p2
    		p2 = tmp
    	tail.next = p1
    	head.next = None
    	return tail 
    
    # @param {ListNode} head
    # @return {boolean}
    def isPalindrome(self, head):
    
    	if head is None or head.next is None: return True
    
    	p1, p2, even = head, head, False
    	while p2.next:		        
    		p1 = p1.next
    		p2 = p2.next
    		if p2.next: p2 = p2.next 
    		else: even = True
    
    	if head.val != p2.val: return False
    
    	halfMark = p1
    	if even: halfTail = p1
    	else: halfTail = p1.next
    	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 = checkPos1.next 
    		checkPos2 = checkPos2.next
    
    	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.