Check if Linked List is Palindrome | Amazon

Check if Linked List is Palindrome | Amazon

Question

Write a program to check if Linked List is Palindrome or not. For the input: 1221 output must be “It is palindrome”.

 

This is one of the important questions. Asked in companies such as Microsoft, Amazon, Snap deal, Yodlee infotech etc.

Logic

  • Get the data from the user and create a doubly linked list using that. In the previous post, we discussed how to create a list from user data.
  • Now in PalinList() traverse till the end of the list to get the length of the list. We use the length to find the palindrome.
  • Check first and last item. If they are same, increment the first pointer and decrement the last pointer.
  • Repeat the same procedure till we reach the middle.
  • If the Palindrome condition satisfied print ” It is palindrome”.

Program

[code lang=”c”]
<pre class="lang:c decode:true ">#include<stdio.h>
/*Doubly linked list with next and previous pointers*/
struct Node
{
int data;
struct Node* next;
struct Node* previous;
};
void PalinList(struct Node** Head)
{
int length =1,i;
struct Node* last = (struct Node*)malloc(sizeof(struct Node));
struct Node* first = (struct Node*)malloc(sizeof(struct Node));
first = *Head;
last = *Head;
/*Finding length of list*/
while(last->next!=NULL)
{
length++;
last = last->next;
}
/*now ‘last’ points to the last item in the list*/

for(i=0;i<length/2;i++) //loop to check respective items
{
if(first->data!=last->data) //palindrome condition failed
{
printf("Not palindrome");
return;
}
first = first->next; //move one item forward
last = last->previous; //move one item backward
}
printf("It is palindrome"); //list is palidrome
}
void append(struct Node** Head,int data)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = NULL;
temp->previous = NULL;
struct Node* t = *Head;
if(*Head == NULL) //First element in the list (or) head is null
{
*Head = temp;
return;
}
/*travese till end*/
while(t->next!=NULL)
t = t->next;

t->next = temp; //next pointer points to last item
temp->previous = t; //previous pointer of last item points to previous item
}
int main()
{
int n,data,i;
struct Node* head = NULL;
printf("enter n:");
scanf("%d",&n);
printf("enter n elements:");

for( i=0;i<n;i++)
{
scanf("%d",&data);
append(&head,data);
}
/*Passing the head pointer to function*/
PalinList(&head);
}
[/code]

You might also like…

Find the middle element in linked list | Microsoft

Insert a node at a specific position in Linked List

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.

Leave a Reply

Your email address will not be published. Required fields are marked *