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

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.