You are given a singly linked list, determine if it is a palindrome.A palindrome is a word, phrase, number, or other sequences of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization).Write a function that takes the head of a linked list as input and returns True if the linked list is a palindrome, and False otherwise.Sample input:4 //size1 2 2 1 //listOutput:TrueExplanation:The linked list reads the same forward and backward, making it a palindrome.
Question
You are given a singly linked list, determine if it is a palindrome.A palindrome is a word, phrase, number, or other sequences of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization).Write a function that takes the head of a linked list as input and returns True if the linked list is a palindrome, and False otherwise.Sample input:4 //size1 2 2 1 //listOutput:TrueExplanation:The linked list reads the same forward and backward, making it a palindrome.
Solution
Here is a Python solution for the problem:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def is_palindrome(head):
# Initialize a slow and a fast pointer to find the middle of the list
slow = head
fast = head
stack = []
# Push all elements till the middle of the list to a stack
while fast is not None and fast.next is not None:
stack.append(slow.data)
slow = slow.next
fast = fast.next.next
# If the list has an odd number of elements, skip the middle element
if fast is not None:
slow = slow.next
# Compare the elements in the stack with the second half of the list
while slow is not None:
if slow.data != stack.pop():
return False
slow = slow.next
return True
This function works by using a slow and a fast pointer to find the middle of the list. It pushes all elements till the middle of the list to a stack. If the list has an odd number of elements, it skips the middle element. Then it compares the elements in the stack with the second half of the list. If all elements match, the list is a palindrome.
Similar Questions
Given the head of a singly linked list, return true if it is a palindrome or false otherwise. Example 1:Input: head = [1,2,2,1]Output: trueExample 2:Input: head = [1,2]Output: false
Given a linked list with string data, check whether the combined string formed is palindrome. If the combined string is palindrome then return true otherwise return false.Example:Input:Output : trueExplanation: As string "abcddcba" is palindrome the function should return true.Input:Output : falseExplanation: As string "abcdba" is not palindrome the function should return false.Expected Time Complexity: O(n)Expected Auxiliary Space: O(n)Constraints:1 <= Node.data.length<= 1031<=list.length<=103
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.Given a string s, return true if it is a palindrome, or false otherwise. Example 1:Input: s = "A man, a plan, a canal: Panama"Output: trueExplanation: "amanaplanacanalpanama" is a palindrome.Example 2:Input: s = "race a car"Output: falseExplanation: "raceacar" is not a palindrome.Example 3:Input: s = " "Output: trueExplanation: s is an empty string "" after removing non-alphanumeric characters.Since an empty string reads the same forward and backward, it is a palindrome. Constraints:1 <= s.length <= 2 * 105s consists only of printable ASCII characters.
Given an integer x, return true if x is a palindrome, and false otherwise. Example 1:Input: x = 121Output: trueExplanation: 121 reads as 121 from left to right and from right to left.Example 2:Input: x = -121Output: falseExplanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.Example 3:Input: x = 10Output: falseExplanation: Reads 01 from right to left. Therefore it is not a palindrome.
Write a python program to check the given string is palindrome or not.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.