💡 Problem Formulation: Given a singly linked list, the task is to determine whether the sequence of elements forms a palindrome. A palindrome is a sequence that reads the same forward and backward. For instance, if the linked list is 1 -> 2 -> 2 -> 1, then the output should be True because when read in reverse, the sequence remains 1 -> 2 -> 2 -> 1.
Method 1: Use a Stack
To determine if a linked list forms a palindrome, one straightforward method is to use a stack data structure. Traverse the linked list and push each element onto the stack. Then, traverse the list again and compare each element with the top of the stack. If all elements match, it forms a palindrome. This method is robust but uses extra space proportional to the length of the list.
♥️ Info: Are you AI curious but you still have to create real impactful projects? Join our official AI builder club on Skool (only $5): SHIP! - One Project Per Month
Here’s an example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def is_palindrome(head):
stack = []
current = head
while current:
stack.append(current.data)
current = current.next
current = head
while current:
if current.data != stack.pop():
return False
current = current.next
return True
# Example linked list: 1 -> 2 -> 2 -> 1
head = Node(1)
head.next = Node(2)
head.next.next = Node(2)
head.next.next.next = Node(1)
print(is_palindrome(head))
Output: True
This code snippet defines a Node class for linked list nodes and an is_palindrome() function to check for palindrome. It fills the stack with the data of each node and then verifies by popping from the stack while traversing the list a second time. If all items match, it returns True.
Method 2: Reversed List Comparison
Another technique involves creating a reversed copy of the linked list and comparing the original list with the reversed list to see if they are identical. While space-efficient, this solution creates an entirely new list and requires additional operations for reversing the list, which may not be optimal for very long lists.
Here’s an example:
def is_palindrome(head):
vals = []
current = head
while current:
vals.append(current.data)
current = current.next
return vals == vals[::-1]
# Example linked list: 1 -> 2 -> 2 -> 1
head = Node(1)
head.next = Node(2)
head.next.next = Node(2)
head.next.next.next = Node(1)
print(is_palindrome(head))
Output: True
In this code snippet, the is_palindrome() function collects all values of the linked list into an array and then compares the array with its reversed version using slice notation. If the two arrays are identical, the linked list is a palindrome.
Method 3: Recursive Approach
To check for a palindrome in a more space-efficient way, we can use recursion. The recursion traverses the list, and on the way back checks each node against its corresponding node from the beginning of the list. This method saves space but is more complex to implement and understand.
Here’s an example:
def is_palindrome_recurse(head, length):
if head is None or length 2 -> 2 -> 1
head = Node(1)
head.next = Node(2)
head.next.next = Node(2)
head.next.next.next = Node(1)
print(is_palindrome(head))
Output: True
This snippet features a recursive function is_palindrome_recurse(), which returns a tuple indicating whether the sublist is a palindrome and the next node to compare. The function is_palindrome() prepares the length of the list and initiates recursion.
Method 4: Two-Pointer Approach
The two-pointer approach involves finding the middle of the linked list, reversing the second half of the list, and then comparing the first half with the reversed second half. This approach solves the problem in-place and only requires O(1) additional space, but modifies the input list, which might not be desirable.
Here’s an example:
def reverse_list(head):
prev = None
while head:
temp = head.next
head.next = prev
prev = head
head = temp
return prev
def is_palindrome(head):
slow = fast = head
# Find the middle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse the second half
slow = reverse_list(slow)
fast = head
# Compare the two halves
while slow:
if slow.data != fast.data:
return False
slow = slow.next
fast = fast.next
return True
# Example linked list: 1 -> 2 -> 2 -> 1
head = Node(1)
head.next = Node(2)
head.next.next = Node(2)
head.next.next.next = Node(1)
print(is_palindrome(head))
Output: True
This code defines a helper function reverse_list() to reverse the second half of the linked list. The main is_palindrome() function then uses a slow and fast pointer to find the middle of the list, reverse the second half, and finally compares the two halves for equality.
Bonus One-Liner Method 5: Convert to Python List
A quick one-liner method can be used during prototyping or cases where efficiency is not a priority. Convert the linked list into a Python list and check if it is equal to its reversed version. This approach is not space-efficient and mainly serves for quick checks or small lists.
Here’s an example:
is_palindrome = lambda head: [node.data for node in iter(head)] == [node.data for node in reversed(iter(head))] # Example usage with a suitable iterable linked list class print(is_palindrome(head))
Output: True
This one-liner makes use of Python’s list comprehension and reversed() function by turning the linked list into an iteratable object. Note that for this to work, additional implementation is needed to make the linked list iterable.
Summary/Discussion
- Method 1: Use a Stack. Straightforward approach. Easy to implement and understand. Uses extra memory proportional to the length of the list.
- Method 2: Reversed List Comparison. Simplistic, uses Python’s slicing advantages. Creates a new list, which may not be memory efficient.
- Method 3: Recursive Approach. Space efficient. Complexity can make it harder to implement and understand for longer lists. Uses system stack space.
- Method 4: Two-Pointer Approach. In-place solution with O(1) space complexity. Non-destructive version requires list restoration.
- Bonus One-Liner Method 5: Convert to Python List. Useful for quick tests or small lists. Not suitable for production code due to efficiency concerns.