Check if a singly linked list is a palindrome or not in C

Question

I'm trying to check if a singly linked list is a palindrome or not. The constraints are - the algorithm has to be in linear time and constant space.

The basic algorithm I'm using is as below -

1. Use fast & slow pointers to divide the list into two halves.
2. Reverse the second half in-place.
3. Compare the first and second half.
4. Construct back the original list
5. Return the result.

My implementation works for when the list has even number of elements but fails if the number of elements is odd.

/*
 * @brief   Checks if a list is a palindrome or not
 */
bool is_palindrome(node *head)
{
    node *first;                /* Points to head node of 1st half */
    node *second;               /* Points to head node of 2nd half */
    node *f_ptr = head;         /* Fast pointer */
    node *s_ptr = head;         /* Slow pointer */
    node *prev = NULL;          /* Previous to slow pointer */
    bool ret = false;           /* Return value */

    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;
}

Can someone please help me figure out what I am doing wrong while handling the odd number case? The complete implementation of this program can be found here.

Answer 1

Thanks to s7amuser for pointing out the bug. Below is the implementation that works for both even & odd cases.

/*
 * @brief   Checks if a list is a palindrome or not
 */
bool is_palindrome(node *head)
{
    node *first;                /* Points to head node of 1st half */
    node *second;               /* Points to head node of 2nd half */
    node *f_ptr = head;         /* Fast pointer */
    node *s_ptr = head;         /* Slow pointer */
    node *prev = NULL;          /* Previous to slow pointer */
    bool ret = false;           /* Return value */

    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 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);
    }
    /* List with even number of elements */
    else 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);
    }
    return ret;
}