Is Palindrome

Leetcode link: https://leetcode.com/problems/palindrome-linked-list

Question#

Given the head node of a singly linked list, determine if it is a palindrome or not.

A palindrome reads the same from front to back and back to front. Example: racecar or madam or radar or redder.

Method 1 - Using String#

We form a string by iterating through the linked list and then reversing the string to compare with the original.

def is_palindrome(head):
s = ""
curr = head
while curr:
s += curr.data
curr = curr.next
return s == s[::-1]

Overall, analysing the time complexity, we get O(n)for iterating through linked list, O(n) for reversing string. Overall

  • Time complexity: O(n)

Method 2 - Using Stack#

In this method, we use a list as a stack and append to it all the elements while iterating the linked list. Then we compare element by element while iterating the linked list in a second loop.

def is_palindrome(head):
curr = head
stack = []
while curr:
stack.append(curr.data)
curr = curr.next
curr = head
while curr:
if(curr.data != stack.pop()):
return False
curr = curr.next
return True

Analysing this solution, we get O(n) time complexity to iterate the linked list twice.

We also need O(n) space for the stack to store n elements of the linked list.

  • Time complexity: O(n)
  • Space complexity: O(n)

Method 3 - Two Pointers#

Here we use two pointers, p1 and p2 at the start and end of the linked list respectively. We increment p1 and decrement p2 in their positions to check the value.

def is_palindrome(head:
if head is None:
return True
p1 = head
p2 = head
# list to store previous nodes
prev = []
while p2:
prev.append(p2)
p2 = p2.next
# p2 is at the last node
p2 = prev[-1]
# loop with both pointers
count = 1
while(count <= len(prev) // 2 + 1):
if(prev[-count].data != p1.data):
return False
p1 = p1.next
count += 1
return True

Analysing this, we get a time complexity of O(n) as we iterate the linked list fully once with p2 and then again for half of the linked list which is O(n/2).

We also need a space of O(n) as we are storing all the nodes in an array.

  • Time complexity: O(n)
  • Space complexity: O(n)

Method 4 - Two Pointers Optimised#

Here we use still use two pointers, but we attempt to reverse the second half of the linked list and compare it.

For example, if we have a string redder, reversing the second half gives us redred. Now if we have a pointer at the start and the middle, we can increment them step by step and compare the values.

class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if(head is None):
return True
p1 = head
p2 = head
# bring p1 to middle and p2 to end
while p2 and p2.next:
p1 = p1.next
p2 = p2.next.next
# reverse the second half of the linked list
p1 = self.reverse(p1)
# iterate from start to end
p2 = head
while (p1 and p2):
if(p1.val != p2.val):
return False
p1 = p1.next
p2 = p2.next
return True
# Auxillary method to reverse linked list
def reverse(self, head):
if(head is None):
return
prev = None
curr = head
next = head.next
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev

Analysing this, we are iterating the linked list with O(n) time complexity. We are using no auxillary space, hence O(1) space.

  • Time complexity: O(n)
  • Space complexity: O(1)