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
<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); }