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

• 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):

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``````

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

• @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

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