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

<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

Sree Hari Sanjeev

The founder and CEO of Wisdom Overflow. His enthusiasm and effort has taken the blog to next level. You will be motivated just by taking a look at his daily schedule.

Leave a Reply

Your email address will not be published.

19 − nine =