palindrome-linkedlist.c

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

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node* init();
void insert_end(Node *head, int data);
void display(Node *head);
Node* reverse(Node *head);
int is_palindrome(Node *head);

int main() {
    Node *head = init();
    
    insert_end(head, 1);
    insert_end(head, 2);
    insert_end(head, 3);
    insert_end(head, 2);
    insert_end(head, 1);
    
    display(head);
    
    head->next = reverse(head->next);
    display(head);
    
    printf("is palindrome : %s\n", is_palindrome(head->next) ? "true" : "false");

    return 0;
}

Node *init() {
    Node *head = (Node*)calloc(1, sizeof(Node));
    head->next = NULL;
    return head;
}

void insert_end(Node *head, int data) {
    Node *new = (Node*)calloc(1, sizeof(Node));
    new->data = data;
    new->next = NULL;
    
    Node *curr = head;
    while (curr->next != NULL) curr = curr->next;
    
    curr->next = new;
}

void display(Node *head) {
    Node *curr = head->next;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

Node* reverse(Node *head) {
    Node *prev = NULL, *curr = head, *next = NULL;
    
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

int is_palindrome(Node *head) {
    Node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    Node *first_half = head, *second_half = reverse(slow);
    while (second_half) {
        if (first_half->data != second_half->data) return 0;
        first_half = first_half->next;
        second_half = second_half->next;
    }
    
    return 1;
}