Table of Contents
A palindrome is a sequence of characters that is read the same forward and backward. For example, “racecar” is a palindrome.
In the context of a linked list, we can consider it a palindrome if the sequence of values in the list is the same when read from left to right and from right to left.
For example, consider the following linked list:
1 -> 2 -> 3 -> 2 -> 1 -> nullThis linked list is a palindrome because the sequence of values in the list is the same when read from left to right and from right to left: 1, 2, 3, 2, 1.
The goal of this problem is to check whether a given linked list is a palindrome.
1: Check Palindromic Linked List by finding Middle Node
- Traverse the linked list to find the middle node.
- Reverse the second half of the linked list.
- Compare the values in the first half of the linked list with the reversed values in the second half of the linked list.
If the values in both halves of the linked list match, then the linked list is a palindrome. Otherwise, it is not.
The time complexity of this approach is O(n), where n is the number of nodes in the linked list.
The space complexity is O(1), since we only need a constant amount of extra space to keep track of the middle node and to reverse the second half of the linked list.
def is_palindrome(head):
if not head or not head.next:
return True
# Step 1: Find the middle node
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# If the linked list has odd number of nodes, skip the middle node
if fast:
slow = slow.next
# Step 2: Reverse the second half of the linked list
prev = None
curr = slow
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
# Step 3: Compare the values in the first half of the linked list with the reversed values in the second half
left = head
right = prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True2: Check Palindromic Linked List using Stack
We can use a stack to store the values of the first half of the linked list. We start by traversing the linked list to find its length. We then push the first half of the values onto a stack, skipping the middle node if the list has an odd number of nodes.
We then traverse the second half of the linked list, popping values off the stack and comparing them to the values in the second half of the list. If all the values match, then the linked list is a palindrome.
def is_palindrome(head):
if not head or not head.next:
return True
# Find length of the linked list
length = 0
curr = head
while curr:
length += 1
curr = curr.next
stack = []
curr = head
for i in range(length // 2):
stack.append(curr.val)
curr = curr.next
# If the list has an odd number of nodes, skip the middle node
if length % 2 != 0:
curr = curr.next
# Compare values in the second half of the list with the values in the stack
while curr:
if curr.val != stack.pop():
return False
curr = curr.next
return True3: Check Palindromic Linked List using Recursion
We can also use recursion to compare the values in the first half of the linked list with the values in the second half of the list.
We start by recursively traversing the linked list to find the middle node. We then compare the value of the middle node with the value of the node at the end of the first half of the list.
We continue this process recursively for each pair of nodes, moving toward the middle of the list. If all the pairs of nodes match, then the linked list is a palindrome.
def is_palindrome(head):
length = get_length(head)
result = is_palindrome_recurse(head, length)
return result.is_palindrome
def get_length(head):
length = 0
curr = head
while curr:
length += 1
curr = curr.next
return length
def is_palindrome_recurse(head, length):
if not head or length <= 0:
return Result(head, True)
elif length == 1:
return Result(head.next, True)
result = is_palindrome_recurse(head.next, length - 2)
if not result.is_palindrome or not result.node:
return result
result.is_palindrome = head.val == result.node.val
result.node = result.node.next
return result
class Result:
def __init__(self, node, is_palindrome):
self.node = node
self.is_palindrome = is_palindromeThe is_palindrome_recurse function takes in the current node and the length of the remaining list to be checked.
It returns a Result object that contains the current node and whether or not the linked list is a palindrome.
The Result class is a simple class that contains two fields: node, which stores the current node, and is_palindrome, which is a boolean value that indicates whether the linked list is a palindrome.
The time complexity of this solution is O(n), where n is the number of nodes in the linked list. The space complexity is also O(n),
since the function call stack can have up to n/2 frames in the worst case, where n is the number of nodes in the linked list.
Which one is better and optimum
Each of the three methods for checking if a linked list is a palindrome has its own advantages and disadvantages.
The first method using the slow and fast pointers to find the middle node and reverse the second half of the linked list has a space complexity of O(1), which is the most memory efficient solution.
It also only requires a single pass through the linked list, making it faster than the first method. However, it involves modifying the original linked list, which may not be desirable in certain situations.
The second method using a stack is simple and straightforward to implement, and has a space complexity of O(n), where n is the number of nodes in the linked list.
However, it requires two passes through the linked list, which can make it slower than the other methods.
The third method using recursion is a clever way to avoid modifying the original linked list and only requires a single pass through the linked list.
However, it has a space complexity of O(n) due to the recursive call stack, which may not be desirable in some situations.
In terms of time complexity, all three methods have a time complexity of O(n), where n is the number of nodes in the linked list.
Therefore, the choice of which method to use would depend on the specific requirements of the problem and the constraints of the system it is being implemented on.
