Function that checks for palindrome in c

Write a function in C that checks if a singly linked list is a palindrome.

• Prototype: int is_palindrome(listint_t **head);

• Return: 0 if it is not a palindrome, 1 if it is a palindrome

• An empty list is considered a palindrome

First, what is a palindrome:

A palindrome is a word, phrase, number, or sequence of characters that reads the same forward and backward. In other words, it remains the same even when the order of its letters or digits is reversed. Palindromes can be found in various languages and can be formed by combining letters or numbers in different ways.

Here are a few examples of palindromic words:

• "level"

• "radar"

• "madam"

• "deed"

Linked lists can be confusing sometimes and when you think so much about it, you might get frustrated, so always whiteboard first, get a paper and draw the boxes(linked lists) and arrows(pointers) you will figure it out faster. It makes more sense on paper.

Reversing a linked list

listint_t *reverse_list(listint_t **head)
{
    listint_t *prev = NULL;
    listint_t *current = *head;
    listint_t *next = *head;

    while (current != NULL)
    {
        next = next->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    *head = prev;
    return (*head);
}

when reversing a linked list, all you need is three pointers
*next: stores a pointer to the next node
*current: the current node
*prev: stores a pointer to the previous node

Let's go through the code line line

listint_t *prev = NULL;

At initial, prev will be NULL because the aim of reversing a linked list is to make the head NULL and the last node the head.

listint_t *current = *head;
listint_t *next = *head;

next and current pointers point to the head because that's where we will start traversing from.

while (current != NULL)

we keep traversing the loop till we reach the end. you can also say while (next != NULL) it will give the same result too.

next = next->next;

we store the address of the next node so when we set the current node to point to the previous node, we don't lose the reference to the next node. This way, we have a pointer to the next node.

current->next = prev;

Now we set the current node to point to the prev node, in this case, NULL.
As you can see our first node now points to NULL.

prev = current;

now set the prev node to point to the current node, so we can reference it as we move across the node.

current = next;

now set the current node to point to the same address as the next node. Now current and next points to the same node again, and we continue this same(looping) process till we reach the end of the node.

*head = prev;
return (*head);

When we finish traversing the list, current and next nodes will be pointing to NULL and prev will have the address of the last node. So we now set the head to prev and return the head.

Here is the main logic that checks for palindrome

int is_palindrome(listint_t **head)
{
    listint_t *temp = NULL;
    listint_t *mid_node = NULL;
    listint_t *rev_list = NULL;
    int len_list = 0, i;

    /* Empty list or single node list is considered a palindrome */
    if (*head == NULL || (*head)->next == NULL)
        return (1);

    temp = *head;
    /* This gets the size of length of the list */
    while (temp)
    {
        len_list++;
        temp = temp->next;
    }

    temp = *head;

    /* It moves temp to the middle node of the list by iterating (len_list / 2) - 1 times. */
    for (i = 0; i < (len_list / 2) - 1; i++)
        temp = temp->next;

    /* It checks if the list length is even and the middle node and its next node have different values. If so, it returns 0, indicating that the list is not a palindrome. */
    if ((len_list % 2) == 0 && temp->n != temp->next->n)
        return (0);

    /* advances temp to the next node after the middle node */
    /* to be more pecise, it will jump one node after the middle node and point to next */
    temp = temp->next->next;
    /* this reverses the node after the middle node */
    rev_list = reverse_list(&temp);
    mid_node = rev_list;

    temp = *head;
    /* we use rev_list as a condition because if the node is even, its going to reach the end before the original list reach the middle */
    while (rev_list)
    {
        /* Here we can easily compared the two lists and check for palindrome */
        if (temp->n != rev_list->n)
            return (0);
        temp = temp->next;
        rev_list = rev_list->next;
    }
    /* this reverses back the list before the program ends */
    /* recall that the last node before the reverse was made still has a pointer to the next node in line, and we didnt change that so when we reverse the node again, everything will be back to normal */
    reverse_list(&mid_node);

    return (1);
}

The code is straightforward to follow with not much complexity like when I was tackling the reverse function. I have commented through it to explain the process especially the parts that took me a lot of time and much research to figure out