Friedrich Ewald My Personal Website

Leetcode: Palindrome linked list

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:

  1. Find the middle of the list
  2. Reverse the second half of the list
  3. 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. 
# 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:
        p1 = head
        p2 = head
        while p2 is not None and p2.next is not None:
            p1 = p1.next
            p2 = p2.next.next
        
        rev = self.reverse(p1)
        while head is not None and rev is not None:
            if head.val != rev.val:
                return False
            rev = rev.next
            head = head.next
        if head == p1:
            head = None
        return head is None and rev is None
        
    
    def reverse(self, head):
        prev = None
        curr = head
        while curr is not None:
            n = curr.next
            curr.next = prev
            prev = curr
            curr = n
        return prev
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

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.

Related Posts