ADVERTISEMENT
ADVERTISEMENT

C program to check a linked list is palindrome or not

Here, we are going to learn how to check a linked list is palindrome or not using C program?
Submitted by Nidhi, on August 19, 2021

Problem Solution:

Create a linked list, and then check created list is palindrome or not.

Program:

The source code to check a linked list is palindrome or not is given below. The given program is compiled and executed using GCC compile on UBUNTU 18.04 OS successfully.

// C program to check a linked list
// is palindrome or not

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

//Self referential structure to create node.
typedef struct tmp {
    int item;
    struct tmp* next;
} Node;

//structure for create linked list.
typedef struct
    {
    Node* head;
    Node* tail;

} List;

//Initialize List
void initList(List* lp)
{
    lp->head = NULL;
    lp->tail = NULL;
}

//Create node and return reference of it.
Node* createNode(int item)
{
    Node* nNode;

    nNode = (Node*)malloc(sizeof(Node));

    nNode->item = item;
    nNode->next = NULL;

    return nNode;
}

//Add new item at the end of list.
void addAtTail(List* lp, int item)
{
    Node* node;
    node = createNode(item);

    //if list is empty.
    if (lp->head == NULL) {
        lp->head = node;
        lp->tail = node;
    }
    else {
        lp->tail->next = node;
        lp->tail = lp->tail->next;
    }
}

//Add new item at begning of the list.
void addAtHead(List* lp, int item)
{
    Node* node;
    node = createNode(item);

    //if list is empty.
    if (lp->head == NULL) {
        lp->head = node;
        lp->tail = node;
    }
    else {
        node->next = lp->head;
        lp->head = node;
    }
}

//To print list from start to end of the list.
void printList(List* lp)
{
    Node* node;

    if (lp->head == NULL) {
        printf("\nEmpty List");
        return;
    }

    node = lp->head;

    while (node != NULL) {
        printf("| %05d |", node->item);
        node = node->next;

        if (node != NULL)
            printf("--->");
    }
    printf("\n\n");
}

int isPalindrome(List* lp)
{
    Node* temp;
    int arr[100];

    int flag = 1;
    int count = 0;

    temp = lp->head;

    while (temp != NULL) {
        arr[count++] = temp->item;
        temp = temp->next;
    }

    temp = lp->head;
    count = count - 1;
    while (temp != NULL) {
        if (arr[count--] != temp->item) {
            flag = 0;
            break;
        }
        temp = temp->next;
    }

    return flag;
}

//Main function to execute program.
int main()
{
    List* lp;

    lp = (List*)malloc(sizeof(List));

    initList(lp);

    addAtHead(lp, 100);
    addAtHead(lp, 200);
    addAtHead(lp, 300);
    addAtHead(lp, 200);
    addAtHead(lp, 100);

    printf("List:\n");
    printList(lp);

    if (isPalindrome(lp))
        printf("List is palindrome\n");
    else
        printf("List is not palindrome\n");

    return 0;
}

Output:

List:
| 00100 |--->| 00200 |--->| 00300 |--->| 00200 |--->| 00100 |

List is palindrome

Explanation:

Here, we created a self-referential structure to implement a linked list, a function to add a node at the start and end of the list, a function isPalindrome() to check linked list is palindrome or not. The isPalindrome() function returns 1 if the list is palindrome otherwise it will return 0.

In the main() function, we created a linked list. Then we checked the given list is palindrome or not using the isPalindrome() function and printed the appropriate message.

ADVERTISEMENT
ADVERTISEMENT


Comments and Discussions!



ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.