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:
- Find the middle of the list
- Reverse the second half of the list
- Iterate over both lists simulatenously, comparing the elements
# 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.