A palindrome is a sequence of numbers or characters that reads the same forwards and backwards. For example, words like “radar” or “madam” are palindromes. The sequence of letters are the same when read in forward direction or in reverse direction.
In the context of linked lists, checking if a linked list is a palindrome presents an interesting challenge. Unlike strings or arrays, linked lists don’t allow easy access to elements by index, making the traditional palindrome-checking methods less straightforward. The problem of determining whether a singly linked list is a palindrome requires careful consideration of the data structure’s properties and efficient traversal techniques. This problem not only tests one’s understanding of linked lists but also encourages creative problem-solving to achieve an optimal solution.
Given a singly linked list, determine whether it is a palindrome. Below are some of the examples:
Example 1:
Input: 1 -> 2 -> 2 -> 1
Output: True
Reason: The list reads the same forward and backward.
Example 2:
Input: 1 -> 2 -> 3 -> 2 -> 1
Output: True
Reason: The list reads the same forward and backward.
Example 3:
Input: 1 -> 2 -> 3 -> 4
Output: False
Reason: The list does not read the same forward and backward.
Constraints and Assumptions:
The linked list is singly linked, meaning each node only has a reference to the next node.
An empty list or a list with a single node is considered a palindrome.
The length of the list is not known in advance.
The head of the list is given as input.
We should aim for an O(n) time complexity solution, where n is the number of nodes in the list.
We should strive for an O(1) space complexity solution, although some approaches may use O(n) space.
This problem challenges us to think about how to compare elements from the beginning and end of a linked list efficiently, given that we can only traverse forward and don’t have direct access to elements by index.
Approaches to Solve the Problem
Brute Force Approach
The brute force approach to check if a linked list is a palindrome involves converting the linked list to an array or a string, and then using standard palindrome-checking techniques.
Below are the algorithm steps for this approach:
Traverse the linked list and copy each node’s value into an array or string.
Use two pointers, one starting from the beginning and one from the end of the array/string.
Move these pointers towards the center, comparing the elements at each step. Stop when both the pointers meet or cross each other.
If all comparisons match, the linked list is a palindrome; otherwise, it’s not.
Time and Space Complexity:
Time Complexity: O(n), where n is the number of nodes in the linked list. The is because we traverse the list once to create the array/string which takes O(n) time and then we then compare elements, which takes at most n/2 comparisons.
Space Complexity: O(n) as we create an additional data structure that stores all n elements of the linked list.
Below is the implementation of this approach in different programming languages:
# Definition of the Node class for the linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Helper function to create a linked list
def create_linked_list(values):
if not values:
return None
head = Node(values[0])
current = head
for value in values[1:]:
current.next = Node(value)
current = current.next
return head
# Helper function to print the linked list
def print_linked_list(head):
current = head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
def is_palindrome(head):
# Step 1: Traverse the linked list
# and copy values to an array
values = []
current = head
while current:
values.append(current.data)
current = current.next
# Step 2 & 3: Use two pointers to compare elements
left = 0
right = len(values) - 1
while left < right:
if values[left] != values[right]:
# Step 4: If any comparison fails,
# it's not a palindrome
return False
left += 1
right -= 1
# Step 4: If all comparisons match,
# it's a palindrome
return True
# Example usage
example_values = [1, 2, 3, 2, 1]
head = create_linked_list(example_values)
print("Original Linked List:")
print_linked_list(head)
result = is_palindrome(head)
print(f"Is the linked list a palindrome? {result}")
#include <iostream>
#include <vector>
using namespace std;
// Definition of the Node class for the linked list
class Node {
public:
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
// Helper function to create a linked list
Node* create_linked_list(const vector<int>& values) {
if (values.empty()) {
return nullptr;
}
Node* head = new Node(values[0]);
Node* current = head;
for (size_t i = 1; i < values.size(); i++) {
current->next = new Node(values[i]);
current = current->next;
}
return head;
}
// Helper function to print the linked list
void print_linked_list(Node* head) {
Node* current = head;
while (current) {
cout << current->data << " -> ";
current = current->next;
}
cout << "None" << endl;
}
// Helper function to free the memory allocated for the linked list
void free_linked_list(Node* head) {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
}
bool is_palindrome(Node* head) {
// Step 1: Traverse the linked list
// and copy values to a vector
vector<int> values;
Node* current = head;
while (current) {
values.push_back(current->data);
current = current->next;
}
// Step 2 & 3: Use two pointers to compare elements
int left = 0;
int right = values.size() - 1;
while (left < right) {
if (values[left] != values[right]) {
// Step 4: If any comparison fails,
// it's not a palindrome
return false;
}
left++;
right--;
}
// Step 4: If all comparisons match,
// it's a palindrome
return true;
}
int main() {
// Example usage
vector<int> example_values = {1, 2, 3, 2, 1};
Node* head = create_linked_list(example_values);
cout << "Original Linked List:" << endl;
print_linked_list(head);
bool result = is_palindrome(head);
cout << "Is the linked list a palindrome? " << (result ? "true" : "false") << endl;
// Free the memory allocated for the linked list
free_linked_list(head);
return 0;
}
// Definition of the Node class for the linked list
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Helper function to create a linked list
function createLinkedList(values) {
if (!values.length) {
return null;
}
let head = new Node(values[0]);
let current = head;
for (let i = 1; i < values.length; i++) {
current.next = new Node(values[i]);
current = current.next;
}
return head;
}
// Helper function to print the linked list
function printLinkedList(head) {
let current = head;
let result = '';
while (current) {
result += current.data + ' -> ';
current = current.next;
}
result += 'None';
console.log(result);
}
function isPalindrome(head) {
// Step 1: Traverse the linked list
// and copy values to an array
let values = [];
let current = head;
while (current) {
values.push(current.data);
current = current.next;
}
// Step 2 & 3: Use two pointers to compare elements
let left = 0;
let right = values.length - 1;
while (left < right) {
if (values[left] !== values[right]) {
// Step 4: If any comparison fails,
// it's not a palindrome
return false;
}
left++;
right--;
}
// Step 4: If all comparisons match,
// it's a palindrome
return true;
}
// Example usage
let exampleValues = [1, 2, 3, 2, 1];
let head = createLinkedList(exampleValues);
console.log("Original Linked List:");
printLinkedList(head);
let result = isPalindrome(head);
console.log("Is the linked list a palindrome? " + result);
import java.util.ArrayList;
import java.util.List;
public class Main {
// Definition of the Node class for the linked list
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
// Helper function to create a linked list
static Node createLinkedList(int[] values) {
if (values == null || values.length == 0) {
return null;
}
Node head = new Node(values[0]);
Node current = head;
for (int i = 1; i < values.length; i++) {
current.next = new Node(values[i]);
current = current.next;
}
return head;
}
// Helper function to print the linked list
static void printLinkedList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
static boolean isPalindrome(Node head) {
// Step 1: Traverse the linked list
// and copy values to an array
List<Integer> values = new ArrayList<>();
Node current = head;
while (current != null) {
values.add(current.data);
current = current.next;
}
// Step 2 & 3: Use two pointers to compare elements
int left = 0;
int right = values.size() - 1;
while (left < right) {
if (!values.get(left).equals(values.get(right))) {
// Step 4: If any comparison fails,
// it's not a palindrome
return false;
}
left++;
right--;
}
// Step 4: If all comparisons match,
// it's a palindrome
return true;
}
public static void main(String[] args) {
// Example usage
int[] exampleValues = {1, 2, 3, 2, 1};
Node head = createLinkedList(exampleValues);
System.out.println("Original Linked List:");
printLinkedList(head);
boolean result = isPalindrome(head);
System.out.println("Is the linked list a palindrome? " + result);
}
}
You can also implement a similar approach by duplicating the given linked list into another linked list, reverse the duplicated linked list, and then compare values in both the linked lists from the start.
Comments on this Approach:
This approach is straightforward and easy to implement.
It works well for small to medium-sized lists.
The main drawback is the O(n) space complexity, which can be problematic for very large lists.
While not the most efficient in terms of space, it’s a good starting point and can be useful in scenarios where memory isn’t a constraint.
Using Extra Space (Stack)
Another approach to solve this problem involves using a stack data structure. This method leverages the Last-In-First-Out (LIFO) property of stacks to compare the first half of the linked list with the second half in reverse order.
The algorithm steps are as follows:
Traverse the linked list to find its length.
Create an empty stack.
Traverse the linked list again, pushing the first half of the elements onto the stack.
If the list has an odd number of elements, skip the middle element.
Continue traversing the remaining half of the list, comparing each element with the top of the stack.
If at any point the comparison fails, return false.
If all comparisons succeed, return true.
Time and Space Complexity:
Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list twice: once to find its length and once to perform the palindrome check.
Space Complexity: O(n/2), which simplifies to O(n). We use a stack to store half of the list’s elements.
Below is the implementation of this approach in various programming languages:
# Definition of the Node class for the linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Helper function to create a linked list
def create_linked_list(values):
if not values:
return None
head = Node(values[0])
current = head
for value in values[1:]:
current.next = Node(value)
current = current.next
return head
# Helper function to print the linked list
def print_linked_list(head):
current = head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Function to check if the linked list is palindrome
def is_palindrome(head):
# Step 1: Traverse the linked list to find its length
length = 0
current = head
while current:
length += 1
current = current.next
# Step 2: Create an empty stack
stack = []
# Step 3: Traverse the linked list again,
# pushing the first half of the elements onto the stack
current = head
for _ in range(length // 2):
stack.append(current.data)
current = current.next
# Step 4: If the list has an odd number of elements,
# skip the middle element
if length % 2 != 0:
current = current.next
# Step 5 & 6: Continue traversing the remaining half of the list,
# comparing each element with the top of the stack
while current:
if current.data != stack.pop():
return False # Comparison failed, not a palindrome
current = current.next
# Step 7: If all comparisons succeed, return True
return True
# Example usage
values = [1, 2, 3, 2, 1]
head = create_linked_list(values)
print("Original linked list:")
print_linked_list(head)
result = is_palindrome(head)
print(f"Is the linked list a palindrome? {result}")
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// Definition of the Node class for the linked list
class Node {
public:
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// Helper function to create a linked list
Node* create_linked_list(const vector<int>& values) {
if (values.empty()) {
return nullptr;
}
Node* head = new Node(values[0]);
Node* current = head;
for (size_t i = 1; i < values.size(); i++) {
current->next = new Node(values[i]);
current = current->next;
}
return head;
}
// Helper function to print the linked list
void print_linked_list(Node* head) {
Node* current = head;
while (current) {
cout << current->data << " -> ";
current = current->next;
}
cout << "None" << endl;
}
// Function to free the memory allocated for the linked list
void free_linked_list(Node* head) {
Node* current = head;
while (current) {
Node* temp = current;
current = current->next;
delete temp;
}
}
// Function to check if the linked list is palindrome
bool is_palindrome(Node* head) {
// Step 1: Traverse the linked list to find its length
int length = 0;
Node* current = head;
while (current) {
length++;
current = current->next;
}
// Step 2: Create an empty stack
stack<int> stack;
// Step 3: Traverse the linked list again,
// pushing the first half of the elements onto the stack
current = head;
for (int i = 0; i < length / 2; i++) {
stack.push(current->data);
current = current->next;
}
// Step 4: If the list has an odd number of elements,
// skip the middle element
if (length % 2 != 0) {
current = current->next;
}
// Step 5 & 6: Continue traversing the remaining half of the list,
// comparing each element with the top of the stack
while (current) {
if (current->data != stack.top()) {
return false; // Comparison failed, not a palindrome
}
stack.pop();
current = current->next;
}
// Step 7: If all comparisons succeed, return true
return true;
}
int main() {
// Example usage
vector<int> values = {1, 2, 3, 2, 1};
Node* head = create_linked_list(values);
cout << "Original linked list:" << endl;
print_linked_list(head);
bool result = is_palindrome(head);
cout << "Is the linked list a palindrome? " << (result ? "true" : "false") << endl;
// Free the allocated memory
free_linked_list(head);
return 0;
}
// Definition of the Node class for the linked list
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Helper function to create a linked list
function createLinkedList(values) {
if (!values.length) {
return null;
}
let head = new Node(values[0]);
let current = head;
for (let i = 1; i < values.length; i++) {
current.next = new Node(values[i]);
current = current.next;
}
return head;
}
// Helper function to print the linked list
function printLinkedList(head) {
let current = head;
let result = '';
while (current) {
result += current.data + ' -> ';
current = current.next;
}
console.log(result + 'None');
}
// Function to check if the linked list is palindrome
function isPalindrome(head) {
// Step 1: Traverse the linked list to find its length
let length = 0;
let current = head;
while (current) {
length++;
current = current.next;
}
// Step 2: Create an empty stack
let stack = [];
// Step 3: Traverse the linked list again,
// pushing the first half of the elements onto the stack
current = head;
for (let i = 0; i < Math.floor(length / 2); i++) {
stack.push(current.data);
current = current.next;
}
// Step 4: If the list has an odd number of elements,
// skip the middle element
if (length % 2 !== 0) {
current = current.next;
}
// Step 5 & 6: Continue traversing the remaining half of the list,
// comparing each element with the top of the stack
while (current) {
if (current.data !== stack.pop()) {
return false; // Comparison failed, not a palindrome
}
current = current.next;
}
// Step 7: If all comparisons succeed, return True
return true;
}
// Example usage
let values = [1, 2, 3, 2, 1];
let head = createLinkedList(values);
console.log("Original linked list:");
printLinkedList(head);
let result = isPalindrome(head);
console.log("Is the linked list a palindrome? " + result);
import java.util.Stack;
public class Main {
// Definition of the Node class for the linked list
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
// Helper function to create a linked list
static Node createLinkedList(int[] values) {
if (values == null || values.length == 0) {
return null;
}
Node head = new Node(values[0]);
Node current = head;
for (int i = 1; i < values.length; i++) {
current.next = new Node(values[i]);
current = current.next;
}
return head;
}
// Helper function to print the linked list
static void printLinkedList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
// Function to check if the linked list is palindrome
static boolean isPalindrome(Node head) {
// Step 1: Traverse the linked list to find its length
int length = 0;
Node current = head;
while (current != null) {
length++;
current = current.next;
}
// Step 2: Create an empty stack
Stack<Integer> stack = new Stack<>();
// Step 3: Traverse the linked list again,
// pushing the first half of the elements onto the stack
current = head;
for (int i = 0; i < length / 2; i++) {
stack.push(current.data);
current = current.next;
}
// Step 4: If the list has an odd number of elements,
// skip the middle element
if (length % 2 != 0) {
current = current.next;
}
// Step 5 & 6: Continue traversing the remaining half of the list,
// comparing each element with the top of the stack
while (current != null) {
if (current.data != stack.pop()) {
return false; // Comparison failed, not a palindrome
}
current = current.next;
}
// Step 7: If all comparisons succeed, return true
return true;
}
public static void main(String[] args) {
// Example usage
int[] values = {1, 2, 3, 2, 1};
Node head = createLinkedList(values);
System.out.println("Original linked list:");
printLinkedList(head);
boolean result = isPalindrome(head);
System.out.println("Is the linked list a palindrome? " + result);
}
}
Comments on this Approach:
This method is more space-efficient than the brute force approach, as it only stores half of the elements.
It’s easier to implement than the optimal two-pointer reversal approach.
The stack-based approach is intuitive and can be a good intermediate solution between the brute force and the optimal approach.
While it doesn’t achieve O(1) space complexity, it can be suitable for scenarios where a slight increase in space usage is acceptable for the sake of implementation simplicity.
Optimal Approach (Two-Pointer Technique with List Reversal)
The optimal approach to determine if a linked list is a palindrome uses the two-pointer technique combined with partial reversal of the list. This method achieves O(n) time complexity and O(1) space complexity.
The two-pointer technique involves using two pointers that move at different speeds through the list:
A slow pointer that moves one step at a time
A fast pointer that moves two steps at a time
This allows us to find the middle of the list efficiently. Once we find the middle, we reverse the second half of the list and compare it with the first half.
Algorithm steps:
Initialize two pointers, slow and fast, to the head of the list.
Move slow one step and fast two steps at a time until fast reaches the end or second-to-last node.
slow is now at the middle (or just after the middle for even-length lists).
Reverse the second half of the list, starting from slow.
Compare the reversed second half with the first half of the list.
Re-reverse the second half to restore the original list structure.
Time and Space Complexity:
Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list once to find the middle, once to reverse the second half, and once to compare the halves.
Space Complexity: O(1), as we only use a constant amount of extra space regardless of the input size.
Below is the implementation of this approach in various programming languages:
# Definition of the Node class for the linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Helper function to create a linked list
def create_linked_list(values):
if not values:
return None
head = Node(values[0])
current = head
for value in values[1:]:
current.next = Node(value)
current = current.next
return head
# Helper Function to print the elements of a linked list
def print_linked_list(head):
current = head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Helper Function to reverse a linked list
def reverse_list(head):
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
# Helper Function to compare two linked lists for equality
def compare_lists(list1, list2):
while list1 and list2:
if list1.data != list2.data:
return False
list1 = list1.next
list2 = list2.next
return True
# Function to check if a linked list is a palindrome
def is_palindrome(head):
if not head or not head.next:
return True
# Step 1: Initialize two pointers,
# slow and fast, to the head of the list
slow = fast = head
# Step 2: Move slow pointer one step
# and fast pointer two steps at a time
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Step 3: slow pointer is now at the middle
# (or just after the middle for even-length lists)
# Step 4: Reverse the second half of the list, starting from slow.next
second_half = reverse_list(slow.next)
# Step 5: Compare the reversed second half with the first half of the list
is_palindrome = compare_lists(head, second_half)
# Step 6: Re-reverse the second half to restore the original list structure
slow.next = reverse_list(second_half)
return is_palindrome
# Example usage
values = [1, 2, 3, 2, 1]
head = create_linked_list(values)
print("Original list:")
print_linked_list(head)
result = is_palindrome(head)
print(f"Is the linked list a palindrome? {result}")
print("List after palindrome check (should be unchanged):")
print_linked_list(head)
#include <iostream>
#include <vector>
using namespace std;
// Definition of the Node class for the linked list
class Node {
public:
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// Helper function to create a linked list
Node* create_linked_list(const vector<int>& values) {
if (values.empty()) {
return nullptr;
}
Node* head = new Node(values[0]);
Node* current = head;
for (size_t i = 1; i < values.size(); i++) {
current->next = new Node(values[i]);
current = current->next;
}
return head;
}
// Helper Function to print the elements of a linked list
void print_linked_list(Node* head) {
Node* current = head;
while (current) {
cout << current->data << " -> ";
current = current->next;
}
cout << "nullptr" << endl;
}
// Helper Function to reverse a linked list
Node* reverse_list(Node* head) {
Node* prev = nullptr;
Node* current = head;
while (current) {
Node* next_node = current->next;
current->next = prev;
prev = current;
current = next_node;
}
return prev;
}
// Helper Function to compare two linked lists for equality
bool compare_lists(Node* list1, Node* list2) {
while (list1 && list2) {
if (list1->data != list2->data) {
return false;
}
list1 = list1->next;
list2 = list2->next;
}
return true;
}
// Function to check if a linked list is a palindrome
bool is_palindrome(Node* head) {
if (!head || !head->next) {
return true;
}
// Step 1: Initialize two pointers,
// slow and fast, to the head of the list
Node* slow = head;
Node* fast = head;
// Step 2: Move slow pointer one step
// and fast pointer two steps at a time
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
// Step 3: slow pointer is now at the middle
// (or just after the middle for even-length lists)
// Step 4: Reverse the second half of the list, starting from slow->next
Node* second_half = reverse_list(slow->next);
// Step 5: Compare the reversed second half with the first half of the list
bool is_palindrome = compare_lists(head, second_half);
// Step 6: Re-reverse the second half to restore the original list structure
slow->next = reverse_list(second_half);
return is_palindrome;
}
// Helper function to free the memory allocated for the linked list
void free_linked_list(Node* head) {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
}
int main() {
// Example usage
vector<int> values = {1, 2, 3, 2, 1};
Node* head = create_linked_list(values);
cout << "Original list:" << endl;
print_linked_list(head);
bool result = is_palindrome(head);
cout << "Is the linked list a palindrome? " << (result ? "true" : "false") << endl;
cout << "List after palindrome check (should be unchanged):" << endl;
print_linked_list(head);
// Free the allocated memory
free_linked_list(head);
return 0;
}
// Definition of the Node class for the linked list
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Helper function to create a linked list
function createLinkedList(values) {
if (!values.length) {
return null;
}
let head = new Node(values[0]);
let current = head;
for (let i = 1; i < values.length; i++) {
current.next = new Node(values[i]);
current = current.next;
}
return head;
}
// Helper Function to print the elements of a linked list
function printLinkedList(head) {
let current = head;
let result = '';
while (current) {
result += current.data + ' -> ';
current = current.next;
}
console.log(result + 'None');
}
// Helper Function to reverse a linked list
function reverseList(head) {
let prev = null;
let current = head;
while (current) {
let nextNode = current.next;
current.next = prev;
prev = current;
current = nextNode;
}
return prev;
}
// Helper Function to compare two linked lists for equality
function compareLists(list1, list2) {
while (list1 && list2) {
if (list1.data !== list2.data) {
return false;
}
list1 = list1.next;
list2 = list2.next;
}
return true;
}
// Function to check if a linked list is a palindrome
function isPalindrome(head) {
if (!head || !head.next) {
return true;
}
// Step 1: Initialize two pointers,
// slow and fast, to the head of the list
let slow = head;
let fast = head;
// Step 2: Move slow pointer one step
// and fast pointer two steps at a time
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
// Step 3: slow pointer is now at the middle
// (or just after the middle for even-length lists)
// Step 4: Reverse the second half of the list, starting from slow.next
let secondHalf = reverseList(slow.next);
// Step 5: Compare the reversed second half with the first half of the list
let isPalindrome = compareLists(head, secondHalf);
// Step 6: Re-reverse the second half to restore the original list structure
slow.next = reverseList(secondHalf);
return isPalindrome;
}
// Example usage
let values = [1, 2, 3, 2, 1];
let head = createLinkedList(values);
console.log("Original list:");
printLinkedList(head);
let result = isPalindrome(head);
console.log("Is the linked list a palindrome? " + result);
console.log("List after palindrome check (should be unchanged):");
printLinkedList(head);
public class Main {
// Definition of the Node class for the linked list
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
// Helper function to create a linked list
static Node createLinkedList(int[] values) {
if (values == null || values.length == 0) {
return null;
}
Node head = new Node(values[0]);
Node current = head;
for (int i = 1; i < values.length; i++) {
current.next = new Node(values[i]);
current = current.next;
}
return head;
}
// Helper Function to print the elements of a linked list
static void printLinkedList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
// Helper Function to reverse a linked list
static Node reverseList(Node head) {
Node prev = null;
Node current = head;
while (current != null) {
Node nextNode = current.next;
current.next = prev;
prev = current;
current = nextNode;
}
return prev;
}
// Helper Function to compare two linked lists for equality
static boolean compareLists(Node list1, Node list2) {
while (list1 != null && list2 != null) {
if (list1.data != list2.data) {
return false;
}
list1 = list1.next;
list2 = list2.next;
}
return true;
}
// Function to check if a linked list is a palindrome
static boolean isPalindrome(Node head) {
if (head == null || head.next == null) {
return true;
}
// Step 1: Initialize two pointers,
// slow and fast, to the head of the list
Node slow = head;
Node fast = head;
// Step 2: Move slow pointer one step
// and fast pointer two steps at a time
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 3: slow pointer is now at the middle
// (or just after the middle for even-length lists)
// Step 4: Reverse the second half of the list, starting from slow.next
Node secondHalf = reverseList(slow.next);
// Step 5: Compare the reversed second half with the first half of the list
boolean isPalindrome = compareLists(head, secondHalf);
// Step 6: Re-reverse the second half to restore the original list structure
slow.next = reverseList(secondHalf);
return isPalindrome;
}
public static void main(String[] args) {
// Example usage
int[] values = {1, 2, 3, 2, 1};
Node head = createLinkedList(values);
System.out.println("Original list:");
printLinkedList(head);
boolean result = isPalindrome(head);
System.out.println("Is the linked list a palindrome? " + result);
System.out.println("List after palindrome check (should be unchanged):");
printLinkedList(head);
}
}
Comments on this Approach:
This is the most efficient solution in terms of both time and space complexity.
It modifies the original list structure (though it can be restored).
The implementation is more complex compared to the previous approaches.
This method is particularly useful when working with large lists or in memory-constrained environments.
Care must be taken to handle edge cases like empty lists, single-node lists, and even vs. odd-length lists.
Applications
Palindromes have several interesting real-world applications across different fields, from computer science to molecular biology. Here are some examples:
DNA Sequences & Genetics: In molecular biology, palindromic sequences of nucleotides (DNA or RNA) play a crucial role. These sequences are symmetrical, meaning they read the same forward and backward, which allows certain enzymes to recognize and cut DNA at specific points. This is key to genetic engineering, cloning, and genome editing techniques.
Error-Correcting Codes: In digital communication, palindromes are used in some error-correcting codes to detect transmission errors. The symmetry of palindromes helps in verifying data integrity by ensuring that the data conforms to certain palindromic patterns, reducing the chances of miscommunication.
Symmetric Keys in Cryptography: The symmetric properties of palindromes can play a role in cryptographic algorithms and hash functions. While palindromes themselves aren’t used for encryption, understanding symmetrical structures helps in analyzing weaknesses in encryption schemes that may be vulnerable due to structural repetition.
Data Compression Algorithms: Some compression techniques use palindrome detection to identify repeating patterns and reduce the overall size of the source data.
Related Problems
Several problems are related to or build upon the concept of palindrome checking in linked lists. Here are some notable examples:
Doubly Linked List Palindrome Checking: This problem involves determining if a doubly linked list is a palindrome. The solution can be more efficient than for singly linked lists, as we can traverse from both ends simultaneously without needing to reverse any part of the list.
Reverse a Linked List: This is a fundamental operation used in the optimal solution for the palindrome problem. It involves changing the direction of links between nodes.
Find the Middle of a Linked List: Another key component of the optimal palindrome solution. This problem introduces the concept of using fast and slow pointers.
Palindrome Partitioning: Given a linked list, partition it such that every sub list of the partition is a palindrome.
Longest Palindromic Substring: Find the longest sub list in a given linked list that is also a palindrome. This problem applies palindrome checking to all possible substrings.
Palindrome Linked List II: A variation where you need to determine if a given linked list can be made into a palindrome by removing at most one node.
These problems build upon similar concepts and techniques used in checking palindromes in linked lists, such as two-pointer techniques, list reversal, and careful manipulation of linked structures.