5 Best Ways to Check Whether a Singly Linked List is a Palindrome in Python

Rate this post

πŸ’‘ 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.