Python Program to Check if a Linked List is a Palindrome

Overview

This Python program checks if a given singly linked list is a palindrome. A palindrome is a sequence of elements that reads the same forward and backward.

Program Explanation

The structure of the program includes a Node class to represent a node in the linked list and a function to check if the linked list is a palindrome. The program uses a two-pointer approach along with list reversal to efficiently determine if the list is a palindrome.

Steps Involved:

1. Create a class Node to represent the elements of the linked list. Each node has two attributes: data (the value of the node) and next (pointer to the next node).
2. Create a function is_palindrome that takes the head of a linked list and checks if it’s a palindrome.
3. Find the middle of the linked list using two pointers: slow and fast. The slow pointer moves one step at a time, and the fast pointer moves two steps at a time.
4. Reverse the second half of the linked list after finding the middle.
5. Compare the first half and the reversed second half of the linked list. If they are identical, the linked list is a palindrome.

Python Code


class Node:
"""
Node class to represent a linked list node.
Each node contains the data and a pointer to the next node.
"""
def __init__(self, data):
self.data = data
self.next = None

def reverse_list(head):
“””
Reverse a linked list.

:param head: Head node of the linked list
:return: New head of the reversed linked list
“””
prev = None
current = head
while current is not None:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev

def is_palindrome(head):
“””
Check if the linked list is a palindrome.

:param head: Head node of the linked list
:return: True if the list is a palindrome, False otherwise
“””
if head is None or head.next is None:
return True

# Step 1: Find the middle of the linked list
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next

# Step 2: Reverse the second half of the linked list
second_half = reverse_list(slow)

# Step 3: Compare the first half and the reversed second half
first_half = head
while second_half is not None:
if first_half.data != second_half.data:
return False
first_half = first_half.next
second_half = second_half.next

return True

# Helper function to print a linked list
def print_linked_list(head):
“””
Print the elements of a linked list starting from the head node.

:param head: Head node of the linked list
“””
current = head
while current is not None:
print(current.data, end=” -> “)
current = current.next
print(“None”)

# Example usage:
# Create a palindrome linked list
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(“Original Linked List:”)
print_linked_list(head)

# Check if the linked list is a palindrome
if is_palindrome(head):
print(“The linked list is a palindrome.”)
else:
print(“The linked list is not a palindrome.”)

Program Explanation

This Python program defines the following:

• Node class: Each node in the linked list contains a value (data) and a reference to the next node (next).
• reverse_list function: Reverses a linked list by iterating through the list and reversing the next pointers of each node.
• is_palindrome function: Checks if the linked list is a palindrome by finding the middle, reversing the second half, and comparing the two halves.
• print_linked_list function: A utility function to display the linked list before performing the palindrome check.

Example Output

Given the linked list:

• 1 -> 2 -> 3 -> 2 -> 1 -> None

The program will output:

The linked list is a palindrome.