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

You might also like…

Find the middle element in linked list | Microsoft

Insert a node at a specific position in Linked List