Time Complexity: O(N), we traverse the entire linked list twice, once to push all elements into the stack, and once to compare them with the original list.

Space Complexity: O(N), we use a stack that stores all the elements of the linked list, which takes linear space in the worst case.

Optimal Approach

Algorithm

Return true if the list is empty or has only one node, since such lists are palindromes by default.
Use two pointers ‘slow’ and ‘fast’ to find the middle node, where slow moves one step and fast moves two steps at a time.
Reverse the second half of the linked list starting from the node after the middle (slow->next), preparing it for comparison.
Set two pointers: one at the head of the list and the other at the head of the reversed second half, to compare both halves.
Compare both halves node by node; if any mismatch occurs, return false, otherwise continue till the end of either list.
Reverse the second half again to restore the original list structure, and return true if all nodes matched successfully.

Code