💡 Problem Formulation: Determining if a singly linked list is a palindrome involves verifying whether the sequence of data in the nodes reads the same forwards and backwards. For example, given a linked list 1 -> 2 -> 2 -> 1, the desired output would be True as it is symmetrical and thus a palindrome.
Method 1: Using a Stack
This method involves traversing the linked list and pushing all elements onto a stack. By popping elements from the stack and comparing them with the second half of the linked list, we can check for palindrome properties since a stack is a LIFO (Last In, First Out) structure, allowing us to compare elements in reverse.
Here’s an example:
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def is_palindrome(head):
stack = []
slow = fast = head
while fast and fast.next:
stack.append(slow.val)
slow = slow.next
fast = fast.next.next
if fast:
slow = slow.next
while slow:
if stack.pop() != slow.val:
return False
slow = slow.next
return True
# Example LinkedList: 1 -> 2 -> 2 -> 1
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(2)
node4 = ListNode(1)
node1.next = node2
node2.next = node3
node3.next = node4
print(is_palindrome(node1))
Output: True
This code example defines a linked list and a function is_palindrome() which uses a stack to store the first half of the list’s elements. Then it compares these elements with the second half of the list to determine if the linked list is a palindrome.
Method 2: Reversing the Second Half
Method 2 entails reversing the second half of the linked list and then comparing it with the first half. If both halves are identical, the list is a palindrome. This method minimizes space usage since it does not require extra storage for the list’s values.
Here’s an example:
class ListNode:
# ListNode class definition
# ...
def reverse_list(head):
prev = None
current = head
while current:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev
def is_palindrome(head):
slow = fast = head
# Find the mid of the linked list
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse the second half
slow = reverse_list(slow)
# Compare the two halves
while slow:
if head.val != slow.val:
return False
head = head.next
slow = slow.next
return True
# Reuse the previously given example LinkedList and function calls
Output: True
The code defines a function reverse_list() to reverse the second half of the linked list. In the function is_palindrome(), after finding the middle of the list, the second half is reversed and compared with the first half to check for a palindrome.
Method 3: Recursive Approach
A recursive approach can be used to compare the elements from the start and end simultaneously without altering the structure of the linked list. This method is elegant but could use extra stack space due to recursion, which means it might not be the most space-efficient for very long lists.
Here’s an example:
class ListNode:
# ListNode class definition
# ...
def is_palindrome_recursor(left, right):
if not right:
return True, left
result, left = is_palindrome_recursor(left, right.next)
if not result or left.val != right.val:
return False, left
return True, left.next
def is_palindrome(head):
result, _ = is_palindrome_recursor(head, head)
return result
# Reuse the previously given example LinkedList and function calls
Output: True
In this recursive code snippet, is_palindrome_recursor() function traverses the linked list and on its way back it compares each element from the start and end, returning True if it is a palindrome.
Method 4: Optimized Space Approach
This method involves creating a copy of the linked list’s values and then using the two-pointer technique to compare the original list and the copied list simultaneously from outward in. This provides a balance between readability and space efficiency.
Here’s an example:
class ListNode:
# ListNode class definition
# ...
def is_palindrome(head):
values = []
current = head
while current:
values.append(current.val)
current = current.next
left, right = 0, len(values) - 1
while left < right:
if values[left] != values[right]:
return False
left += 1
right -= 1
return True
# Reuse the previously given example LinkedList and function calls
Output: True
The code extracts the list’s values into an array values and then uses the two-pointer technique to check if the list is a palindrome by iterating through the array from both ends.
Bonus One-Liner Method 5: Pythonic Approach
A one-liner in Python can be derived using list comprehension and the all() function. This is a more Pythonic way to check if the list is a palindrome by comparing the values directly while traversing them only once.
Here’s an example:
class ListNode:
# ListNode class definition
# ...
def is_palindrome(head):
values = [node.val for node in iter(lambda: head if head else None, None)]
return values == values[::-1]
# Reuse the previously given example LinkedList and function calls
Output: True
This method converts the singly linked list into a list using list comprehension and then checks if it reads the same forward and backward by comparing the list to its reversed version.
Summary/Discussion
- Method 1: Using a Stack. Very intuitive. Requires extra space proportional to the list size.
- Method 2: Reversing the Second Half. Space-optimized. Modifies the list during processing which could be an issue if the list data must remain unchanged.
- Method 3: Recursive Approach. Elegant and straightforward. Not space-efficient for large lists due to recursion stack space.
- Method 4: Optimized Space Approach. Balances space efficiency with readability. Involves copying the list into an array.
- Method 5: Pythonic Approach. Simple and clean. Relies on Python’s powerful syntax and built-in functions for a concise solution.