(Beats 90%) Python solution using a stack with O(N) time complexity and O(N/2) space complexity


  • 2

    The algorithm has two steps:

    1. Find the midpoint of the linked list
    2. Push the second half values into the stack
    3. Pop values out from the stack, and compare them to the first half of the linked list

    The advantages of this algorithm are we don't need to restore the linked list and the space complexity is acceptable (O(N/2))

    def isPalindrome(self, head):
    
        if not head or not head.next:
            return True
    
        # 1. Get the midpoint (slow)
        slow = fast = cur = head
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        
        # 2. Push the second half into the stack
        stack = [slow.val]
        while slow.next:
            slow = slow.next
            stack.append(slow.val)
    
        # 3. Comparison
        while stack:
            if stack.pop() != cur.val:
                return False
            cur = cur.next
        
        return True

  • 0
    R

    Why not just reverse the first half or the second half? That would be O(1) space


  • 0

    @Rhodey yeah that is better in terms of the space complexity, but we need to restore the order of our linked list after reversing. I am not a fan lol


Log in to reply
 

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