# 5 Best Ways to Check If a Linked List Is a Palindrome in Python

Rate this post

π‘ 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.

Here’s an example:

```class Node:
def __init__(self, data):
self.data = data
self.next = None

stack = []
while current:
stack.append(current.data)
current = current.next
while current:
if current.data != stack.pop():
return False
current = current.next
return True

# Example linked list: 1 -> 2 -> 2 -> 1

```

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 = []
while current:
vals.append(current.data)
current = current.next
return vals == vals[::-1]

# Example linked list: 1 -> 2 -> 2 -> 1

```

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

```

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
return prev

# Find the middle
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 slow.data != fast.data:
return False
slow = slow.next
fast = fast.next
return True

# Example linked list: 1 -> 2 -> 2 -> 1

```

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
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.