Exploring Palindrome Detection in a Linked List with Python

Introduction

A linked list is a popular data structure that consists of a series of nodes, where each node contains both data and a reference (or link) to the next node in the sequence. One common problem in computer science is to determine whether a linked list is a palindrome or not. A palindrome is a sequence of characters or elements that reads the same forward and backward. In this article, we will explore various methods to check if a linked list is a palindrome using Python.

The Node Class

Let’s begin by defining the Node class, which represents each element in the linked list. Each node contains a ‘data’ attribute to hold the value and a ‘next’ attribute to reference the next node in the sequence.

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

Building the Linked List

Before we explore different palindrome-checking methods, we need a function to construct a linked list from a given list of elements.

def create_linked_list(elements):
    head = None
    tail = None
    for data in elements:
        new_node = Node(data)
        if head is None:
            head = new_node
            tail = new_node
        else:
            tail.next = new_node
            tail = new_node
    return head

Method 1: Reverse and Compare

In this approach, we reverse the original linked list and compare the reversed list with the original one to check for a palindrome.

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

def is_palindrome_reverse_compare(head):
    reversed_head = reverse_linked_list(head)
    while head and reversed_head:
        if head.data != reversed_head.data:
            return False
        head = head.next
        reversed_head = reversed_head.next
    return True

Method 2: Using a Stack

This method involves using a stack to store the first half of the linked list’s elements and then comparing the second half with the elements popped from the stack.

def is_palindrome_stack(head):
    slow = head
    fast = head
    stack = []

    while fast and fast.next:
        stack.append(slow.data)
        slow = slow.next
        fast = fast.next.next

    if fast:  # For odd-length linked lists
        slow = slow.next

    while slow:
        if slow.data != stack.pop():
            return False
        slow = slow.next

    return True

Method 3: Using Recursion

In this approach, we use recursion to check for a palindrome by moving the head and tail pointers toward the center.

def isPlaindromeCheck(stack, slow, fast):
    if fast != None:
        slow = slow.next

    while slow != None:
        top = stack.pop()
        if (top != slow.data):
            return False
        slow = slow.next

    return True

def isPalindromeUtil(stack, slow, fast):
    if fast != None:
        if fast.next == None:
            status = isPlaindromeCheck(stack, slow, fast)
            return status
    elif fast == None:
            status = isPlaindromeCheck(stack, slow, fast)
            return status

    stack.append(slow.data)
    result = isPalindromeUtil(stack, slow.next, fast.next.next)

    if result != False:
        return True

    return result

def is_palindrome_recursion(head):
    stack = []
    return isPalindromeUtil(stack, head, head)

Testing the Function

Now you can test any of the three methods to check a linked list is palindrome or not. For example, let’s test the `is_palindrome_reverse_compare` function with a sample linked list.

if __name__ == "__main__":
    elements = [1, 2, 3, 2, 1]
    linked_list = create_linked_list(elements)

    if is_palindrome_reverse_compare(linked_list):
        print("The linked list is a palindrome.")
    else:
        print("The linked list is not a palindrome.")

Output

The linked list is a palindrome.

Complexity Analysis

Method 1: Reverse and Compare

Time Complexity

The time complexity mainly arises from two operations:

Asymptotically, both operations can be considered as O(n/2), but in big O notation, we drop the constant factor, so the overall time complexity remains O(n).

Space Complexity

The space complexity of the “Reverse and Compare” approach is O(1), i.e., constant space.

In this method, we do not use any additional data structures that would consume additional space proportional to the size of the linked list. Instead, we modify the original linked list in place by reversing the second half. The space used for reversing is constant because we only use a few temporary variables to perform the swap of nodes.

Method 2: Using a Stack

Time Complexity

The time complexity arises from two main operations:

Asymptotically, both operations can be considered as O(n/2), but in big O notation, we drop the constant factor, so the overall time complexity remains O(n).

Space Complexity

The space complexity of the “Using a Stack” approach is O(n), where ‘n’ is the number of nodes in the linked list. The space complexity primarily comes from the stack used to store the first half of the linked list.

During the traversal of the first half of the linked list, we push ‘n/2’ elements onto the stack (for even-length linked lists) or ‘(n-1)/2’ elements (for odd-length linked lists). The size of the stack grows linearly with the size of the linked list.

Method 3: Using Recursion

Time Complexity

The time complexity arises from the recursive calls made to compare elements from the beginning and end of the list.

In each recursive call, we perform constant-time operations like comparing node values and updating pointers. The recursive function is called ‘n/2’ times (for even-length linked lists) or ‘(n-1)/2’ times (for odd-length linked lists) as we move towards the center of the list.

Since each recursive call takes O(1) time, and the number of recursive calls is proportional to the number of nodes, the overall time complexity remains O(n).

Space Complexity

The space complexity primarily comes from the recursion stack used during recursive function calls.

In each recursive call, the function saves the state and variables on the stack. The maximum depth of recursion will be ‘n/2’ (for even-length linked lists) or ‘(n-1)/2’ (for odd-length linked lists) since we move towards the center of the list.

Since the space used in the recursion stack grows linearly with the depth of recursion (which is O(n)), the overall space complexity is O(n).

Summary

In this article, we explored different methods to check if a linked list is a palindrome using Python. We defined a Node class to represent elements in the linked list and created a function to build the linked list from a list of elements. Then, we demonstrated three distinct palindrome-checking methods: the reverse and compare approach, the stack method, and the recursive solution.

Each method offers a unique perspective on how to approach this problem efficiently. Understanding these techniques equips programmers with valuable tools to solve similar challenges and showcases the versatility of linked lists as data structures in various applications.

If you have any questions related to this topic, please don’t hesitate to leave your comments below.