Question

Write a complete C program to do the following:(i) Define a function Nodeptr CreateDLL(char str[])which takes a string as parameter and creates a Doubly Linked List of characters and returns the pointer to the first node. (ii) Define a function int IsPalindrome(Nodeptr first)to check whether the string represented by the above doubly linked list pointed to by first, is a palindrome or not and return 1/0 accordingly. Do not use any additional data structure.Write a main function to read a string and create Doubly Linked of characters and check whether the string is a palindrome using above functions. Assume the following structure definition:typedef struct NODE *Nodeptr;struct NODE {

char letter;

Nodeptr llink, rlink;

};

} ;

Answer 1

Complete C code for the question with two functions as described:

#include <stdio.h>
#include <stdlib.h>
#include<string.h>

//structure def
typedef struct NODE *Nodeptr;
struct NODE {
        char letter;
        Nodeptr llink, rlink;
};

/* protypes for functions defined after main */
Nodeptr CreateDLL(char *);
int IsPalindrome(Nodeptr);

//function to create double linked list
Nodeptr CreateDLL(char str[])
{
        int n = strlen(str);
        Nodeptr first = NULL;
        for (int i = 0; i < n; i++)
        {
                Nodeptr new_node = (struct NODE*)malloc(sizeof(struct NODE));

                Nodeptr last = first;
                new_node->letter = str[i];

                new_node->rlink = NULL;

                //if first node is NULL
                if (first == NULL) {
                        new_node->llink = NULL;
                        first = new_node;
                        continue;
                }

                //to get the last node to insert the new char at the end
                while (last->rlink != NULL)
                        last = last->rlink;

                last->rlink = new_node;

                new_node->llink = last;
        }

        return first;
}

//function to check palindrome
int IsPalindrome(Nodeptr first)
{
        Nodeptr last = first;
        while (last->rlink != NULL)
                last = last->rlink;

        while (first != last)
        {
                //return 0 if any character is mismatched
                if (first->letter != last->letter)
                        return 0;

                first = first->rlink;
                if (first == last)
                        break;
                last = last->llink;
        }

        return 1;
}



int main() {
        char str[1000];
        printf("Enter the string to be checked\n");
        scanf("%[^\n]%*c", str);

        Nodeptr first = CreateDLL(str);
        int val = IsPalindrome(first);
        if (val == 1)
                printf("Palindrome.\n");
        else
                printf("Not a plaindrome.\n");

        return 0;
}

EXPLANATION:

In the first function createDLL i have interated through the string and for each character, added it as a node to the end of the double linkedlist and returned the pointer to the first node.

In the second function Ispalindrome i have first extracted the pointer to the last node through while loop after that i have taken the first and the last node and simultaneously checked whether both the letters are same or not if not then return 0 from there onwards else continue untill both last and first become equal, atlast return 1 as we know all the characters are equal if it didn't return 0 earlier.

In the main function i have asked for the string input passed to string to createDLL then passed the first pointer to Ispaplindrome then based on val =1/0 returned printed if it is palindrome or not.

NOTE: If there is any kinf of doubt or problem regarding the code or its explanation please let me know in the comment section and i will resolve that asap and kindly UPVOTE !!