Checking if a singly linked list is palindrome. Solution with O(n) time and O(n) space

My solution to that Leetcode problem which is faster than 99% of Python3 LeetCode submissions.

Checking if a singly linked list is palindrome. Solution with O(n) time and O(n) space
Photo by Chris Ried / Unsplash

Hey everyone, today I encountered this interesting problem at Leetcode.com
and I solved it probably not conventionally, using list and reverse slicing.

My solution is simple and elegant and also very fast comparing to already made submissions (beats 99% of submissions):

    def isPalindrome(self, head: ListNode) -> bool:
        
        curr_node, values = head, []
        
		# storing node values in list
        while curr_node:
            values.append(curr_node.val)
            curr_node = curr_node.next
        
		# actually comparing values for palindrome
        return values == values[::-1]

What puzzled me the most, I didn't find any solution using list and reverse slicing.

Here are the links to solutions I found in Google:

  1. Solution using stack at GeeksForGeeks website
  2. Another wolution with stack at www.educative.io

Why my solution is better

Solution with stack traverses list twice, while in first/second tour appending/popping elements from stack. In essence,
its algorithmic complexity is O(4n) => O(n). Space complexity = O(n) /stack of n elements/.

My solution is also of O(4n) => O(n) algorithmic complexity /traverse list once, append elements, compare list with reversed version/.
Space complexity = O(n) /list of n elements/.

However, actually it beats 98.9% of submissions because list slicing and comparing operations are run by CPython and very fast in Python:
linked list palindrome problem submission result
Here we have another example of difference between theoretical and practical algorithmic complexity.

O(n) with O(1) space solution exists, but it is quite complex and in fact not nearly as fast as provided above. You can find it at GeeksForGeeks webpage
(link 1).

Hope you enjoyed my code and I am waiting for your comments.