[Leetcode/Stack] 234. Palindrome Linked List

💡 Key Idea (using stack):

Use a stack (LIFO) to store the values of the nodes. Then, go through the list again and compare each node’s value with the value popped from the stack. If all match, it's a palindrome.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # Step 1: Traverse the list and push all values onto a stack
        stack = []
        current = head
        while current:
            stack.append(current.val)
            current = current.next

        # Step 2: Traverse the list again and compare with stack (LIFO order)
        current = head
        while current:
            if current.val != stack.pop():
                return False
            current = current.next
            
        return True

🧠 Step-by-Step Explanation:

Let’s use an example:
Input linked list: 1 → 2 → 2 → 1

Step 1: Traverse the list and push values onto a stack

We initialize an empty list stack = [].

We iterate through the linked list:

• Visit node with value 1: stack = [1]
• Visit node with value 2: stack = [1, 2]
• Visit node with value 2: stack = [1, 2, 2]
• Visit node with value 1: stack = [1, 2, 2, 1]

Now the stack contains all values in order of appearance.

Step 2: Traverse the list again and compare values

We start again from the head of the list and pop values from the stack:

• Current node: 1, popped from stack: 1 → ✅ match
• Current node: 2, popped from stack: 2 → ✅ match
• Current node: 2, popped from stack: 2 → ✅ match
• Current node: 1, popped from stack: 1 → ✅ match

If any values didn’t match, we would return False. Since all values match, we return True.

 

⏱️ Time & Space Complexity:

• Time: O(n) — we traverse the list twice
• Space: O(n) — we store all node values in the stack