by Linked List is a data structure used for storing collection of data where successive elements are connected through pointers and the size of linked list can grow or shrink dynamically.
In short, Linked list can be thought as similar to array in which traversal can happen through pointers instead of indexes. Before going ahead have a look into Linked List Basics and Linked List Implementation.
Let’s have a look on basic class definition for Linked List.
class LinkedList
{
public:
int data;
LinkedList* next;
LinkedList (int data);
~LinkedList ();
};
/* Below function will print all nodes in a Linked List */
void print_linked_list (LinkedList* start)
{
if (!start)
{
cout << "Linked list is null, nothing to print" << endl;
return;
}
LinkedList* temp = start;
while (temp)
{
cout << " " << temp -> data;
temp = temp -> next;
}
cout << endl;
}
Check Palindrome in Linked List
A Linked List will be called Palindrome if reverse of the Linked List is similar to actual Linked List. Let’s Look into an example to make it more clear.
As shown in above image, reverse of the above linked list is 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 which is same as original Linked List.
Here we are going to look into the program to find out whether a Linked List is Palindrome or not.
Linked List Palindrome using Linked List Reversal
As shown in above example, one method to find out whether a given Linked List is Palindrome or not is by reversing the Linked List and then comparing the original Linked List nodes with reversed Linked List nodes to determine whether both lists are same or not. If they are same then given Linked List is Palindrome.
In this method, Linked List Reversal is the main logic which need to be understand which is described in Program to reverse a Linked List.
After that comparing of nodes is quite trivial, hence we are not explaining that part here.
Linked List Palindrome using Stack
In this method, we are going to use a Stack to determine whether given Linked List is Palindrome or not. Let’s look into the algorithm for this method.
Algorithm
- Traverse Linked List from Start and push all nodes from Linked List into an Stack.
- Traverse Linked List again from Start and for every node from Linked List
- POP an element from Stack and check whether both are same or not.
- If they are same then continue checking the same till end of List is met.
- If they are different then Linked List is not Palindrome, break and exit from the loop.
- If Linked List end is reached and all nodes are similar to POPPED node from Stack then Linked List is Palindrome.
Few of the functions used below are explained in Stack Implementation and Linked List Implementation. Refer those before going ahead.
Let’s look into the sample code.
void check_palindrome (LinkedList* start)
{
Stack s(20);
LinkedList* temp = start;
while (temp)
{
s.push (temp -> data);
temp = temp -> next;
}
temp = start;
bool isPalindrome = true;
while (temp)
{
if (temp -> data == s.atTop ())
{
temp = temp -> next;
s.pop ();
}
else
{
isPalindrome = false;
break;
}
}
if (isPalindrome)
cout << "Linked List is Palindrome" << endl;
else
cout << "Linked List is not Palindrome" << endl;
}
Let’s define a main function to use above methods.
/* This function will create a Linked List which is not a Palindrome */
LinkedList* create_non_palindrome_linked_list ()
{
LinkedList* start = NULL;
insert_at_begining (&start, 1);
insert_at_begining (&start, 2);
insert_at_begining (&start, 3);
insert_at_begining (&start, 4);
insert_at_begining (&start, 5);
insert_at_begining (&start, 6);
insert_at_begining (&start, 7);
insert_at_begining (&start, 8);
insert_at_begining (&start, 9);
cout << "Length of linked list: " << length_of_linked_list_using_iteration (start) << endl;
print_linked_list (start);
return start;
}
/* This function will create a Linked List which is a Palindrome */
LinkedList* create_palindrome_linked_list ()
{
LinkedList* start = NULL;
insert_at_begining (&start, 1);
insert_at_begining (&start, 2);
insert_at_begining (&start, 3);
insert_at_begining (&start, 4);
insert_at_begining (&start, 5);
insert_at_begining (&start, 4);
insert_at_begining (&start, 3);
insert_at_begining (&start, 2);
insert_at_begining (&start, 1);
cout << "Length of linked list: " << length_of_linked_list_using_iteration (start) << endl;
print_linked_list (start);
return start;
}
int main ()
{
LinkedList* start = create_non_palindrome_linked_list ();
check_palindrome (start);
delete_all_node (&start);
start = create_palindrome_linked_list ();
check_palindrome (start);
delete_all_node (&start);
}
Let’s analyze the output of this main function.
Length of linked list: 9
9 8 7 6 5 4 3 2 1
Linked List is not Palindrome
Length of linked list: 9
1 2 3 4 5 4 3 2 1
Linked List is Palindrome
