cllpalindrome

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

/* Linked list node data structure */
typedef struct _ll_node_ {
    int data;
    struct _ll_node_ *next;
} node;

/*
 * @brief   Prints the state of the list
 */
void print_list(node *head)
{
    node *tmp = head;
    int counter = 0;
    while (tmp)
    {
        printf("Node:\t%d\tValue:\t%d\n", ++counter, tmp->data);
        tmp = tmp->next;
    }
    printf("\n\n");
}

/*
 * @brief   Adds a node at the end of the list
 */
node *add_node(node *head, int data)
{
    node *tmp;
    if (head == NULL)
    {
        head = malloc(sizeof(node));
        assert(head != NULL);
        head->data = data;
        head->next = NULL;
    }
    else
    {
        tmp = head;
        while (tmp->next)
            tmp = tmp->next;
        tmp->next = malloc(sizeof(node));
        assert(tmp->next != NULL);
        tmp = tmp->next;
        tmp->data = data;
        tmp->next = NULL;
    }
    return head;
}

/*
 * @brief   Checks to see if two lists are identical
 */
bool are_identical(node *headA, node *headB)
{
    if (headA == NULL && headB == NULL)
        return true;
    else if (headA != NULL && headB != NULL)
        return (headA->data == headB->data &&\
            are_identical(headA->next, headB->next));
    else
        return false;
}

/*
 * @brief   Utility to reverses a list
 */
node *reverse_list(node **head)
{
    node *prev = NULL;
    node *curr = *head;
    node *next;

    while (curr)
    {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

/*
 * @brief   Checks if a list is a palindrome or not
 */
bool is_palindrome(node *head)
{
    node *first;
    node *second;
    node *f_ptr = head;
    node *s_ptr = head;
    node *prev = NULL;
    bool ret = false;

    while (f_ptr && f_ptr->next && f_ptr->next->next)
    {
        prev = s_ptr;
        s_ptr = s_ptr->next;
        f_ptr = f_ptr->next->next;
    }

    /* List with even number of elements */
    if (!(f_ptr->next->next))
    {
        first = head;
        second = s_ptr->next;
        s_ptr->next = NULL;
        /* Reverse the second half */
        second = reverse_list(&second);
        /* Compare the first & second half */
        ret = are_identical(first, second);
        /* Finally, construct the original list back */
        second = reverse_list(&second);
        s_ptr->next = second;
        print_list(head);
    }
    /* List with odd number of elements */
    if (!(f_ptr->next))
    {
        first = head;
        second = s_ptr->next;
        prev->next = NULL;
        s_ptr->next = NULL;
        /* Reverse the second half */
        second = reverse_list(&second);
        /* Compare the first & second half */
        ret = are_identical(first, second);
        /* Finally, construct the original list back */
        second = reverse_list(&second);
        prev->next = s_ptr; s_ptr->next = second;
        print_list(head);
    }
    return ret;
}

/*
 * @brief   Driver function
 */
int main(int argc, char *argv[])
{
    node *head = NULL;
    int arr[] = { 1, 2, 3, 3, 2, 1};
    int len = sizeof(arr) / sizeof(arr[0]);

    /* Populate the list */
    for (int i = 0; i < len; i++)
        head = add_node(head, arr[i]);

    /* Print the state of the list */
    print_list(head);

    /* Algorithm to check if the list is a palindrome */
    if (is_palindrome(head))
        printf("The link is a palindrome\n");
    else
        printf("The list is NOT a palindrome\n");

    return 0;
}