Write Python Program to Check Whether a Given Linked List is Palindrome

In this tutorial, we will write a Python program to check whether a given linked list is palindrome. A linked list is a data structure used in computer programming for storing and organizing a collection of elements. It consists of a sequence of nodes, where each node stores a data element and a reference (or pointer) to the next node in the sequence.

Unlike arrays, the nodes of a linked list are not stored in contiguous memory locations. Instead, each node is allocated independently in memory and is connected to the next node through the reference or pointer field. It makes it easy to add or remove elements from a linked list, as we only need to update the reference fields of the nodes to reflect the changes.

Solution

First, we will solve this problem using the stack. Let's understand the following example.

Example -

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

def is_palindrome(head):
    if not head or not head.next:
        return True

    # find the middle of the linked list
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # push the first half of the linked list onto a stack
    stack = []
    curr = head
    while curr != slow:
        stack.append(curr.data)
        curr = curr.next

    # compare the second half of the linked list with the stack
    if fast: # odd number of nodes
        curr = slow.next
    else: # even number of nodes
        curr = slow
    while curr:
        if curr.data != stack.pop():
            return False
        curr = curr.next

    return True

one = Node(1)
two = Node(2)
three = Node(3)
four = Node(4)
five = Node(3)
six = Node(2)
seven = Node(1)

one.next = two
two.next = three
three.next = four
four.next = five
six.next = seven
seven.next = one

print(is_palindrome(one))

Output:

True

Explanation -

The above program uses a stack to check if a given linked list is a palindrome. We first define a Node class to represent a single node of the linked list. The is_palindrome() function takes the head node of the linked list as its input and returns True if the linked list is a palindrome, else it returns False.

We first handle the edge cases where the linked list is empty or has only one node, as such lists are always palindromes.

We then find the middle of the linked list using the slow and fast pointers. We traverse the linked list with the fast pointer moving twice as fast as the slow pointer. When the fast pointer reaches the end of the list, the slow pointer points to the middle of the linked list.

We then push the first half of the linked list onto a stack. We traverse the first half of the linked list, starting from the head node and pushing the data elements of the nodes onto the stack.

We then compare the second half of the linked list with the stack. If the number of nodes in the linked list is odd, we start comparing from the node next to the middle node.

Otherwise, we start comparing from the middle node itself. We traverse the second half of the linked list with a pointer curr starting from the node determined above and compare the data elements of the nodes with the elements popped from the stack. If we find any mismatch between the corresponding nodes of the two halves, we know that the linked list is not a palindrome, and we return False.

Otherwise, if we reach the end of the second half without finding any mismatches, we know that the linked list is a palindrome, and we return True.

Example - 2:

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

def is_palindrome(head):
    if not head or not head.next:
        return True
        
    # find the middle of the linked list
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # reverse the second half of the linked list
    prev = None
    curr = slow
    while curr:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next

    # compare the first half with the reversed second half
    p1 = head
    p2 = prev
    while p2:
        if p1.data != p2.data:
            return False
        p1 = p1.next
        p2 = p2.next

    return True

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(2)
head.next.next.next.next = Node(1)

print(is_palindrome(head))

Output:

True

Explanation -

The above code defines a Node class with data and next attributes and a function is_palindrome() that takes a linked list represented by its head node as an argument and returns True if the linked list is a palindrome, i.e., if the sequence of nodes from the head to the tail is the same as the sequence of nodes from the tail to the head, and False otherwise.

The is_palindrome() function first checks if the given linked list is empty or contains only one node, in which case it is trivially a palindrome and returns True.

Otherwise, it finds the middle node of the linked list using a fast-slow pointer technique and reverses the linked list's second half by modifying the nodes' next pointers.

Finally, it compares the data values of the nodes in the first half of the linked list with those of the nodes in the reversed second half and returns True if they all match and False otherwise.

In the example code, a linked list with nodes containing values 1, 2, 3, 2, 1 is created, and the is_palindrome() function is called with the head node of the linked list as an argument. Since the linked list is a palindrome, the function returns True, which is printed to the console.

Time complexity: O(n), where n represents the length of the given linked list.

Conclusion

This tutorial included how to find the palindrome linked list. We have solved this problem using the two approaches. In the first approach, we used the stack and in the second approach, we traverse the linked and check whether a linked list is palindrome.

Next TopicWrite Python Program to Find Greater Element

← prev next →