Welcome to my personal website. I use this space to share some of my thoughts and software that I write in my free time. Sometimes I also publish photos. If you want to get in touch please use LinkedIn or Mastodon.
Given the head of a linked list, determine if the linked list is a palindrome and return True if it is, False otherwise. For added difficulty, find an algorithm that runs in O(n) and uses O(1) space.
The idea to solving this problem can be written as three distinct steps:
Find the middle of the list
Reverse the second half of the list
Iterate over both lists simulatenously, comparing the elements
Finding the middle can be achieved via slow/fast pointer. Reversing should be done iteratively because each recursion step costs memory. Finally we can set two pointers and compare each element. At the final step we need to check if we arrived at the second half or somewhere else.
Runtime: 1729 ms, faster than 12.02% of Python3 online submissions for Palindrome Linked List. Memory Usage: 39.1 MB, less than 77.96% of Python3 online submissions for Palindrome Linked List.
About the author
Friedrich Ewald is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.