An efficient function to check if a singly linked list is a palindrome or not in C

Question

I came up with a solution that can check if a singly list is a palindrome or not. but the solution is not efficient enough. Please i need a suggestion, thanks in advance.

Here is the code:

int is_palindrome(listint_t **head)
{
    listint_t *current, *temp1, *temp2;
    int first_elem, second_elem;

    if (*head == NULL || (*head)->next == NULL || (*head)->n == (*head)->next->n)
        return (1);

    current = *head;
    first_elem = (*head)->n;
    while (current->next->next != NULL)
        current = current->next;

    second_elem = current->next->n;
    if (first_elem == second_elem)
    {
        temp1 = *head;
        *head = (*head)->next;
        temp2 = current->next;
        current->next = NULL;
        free(temp1);
        free(temp2);
        return (is_palindrome(head));
    }
    else
        return (0);
}

Do you keep track of how many elements you have in that linked list? — Ted Lyngmo, Aug 29 '22 at 10:09
@Bayeroabdul Due to this statement if (*head == NULL || (*head)->next == NULL || (*head)->n == (*head)->next->n) return (1); the function returns true for the list 1->1->2 though such a list is not a palindrome. — Vlad from Moscow, Aug 29 '22 at 10:17
Not sure what the point is of using double pointers If you are erasing the list from both ends... Do you want to retain access to the portion in the middle that is not palindromic? (And, btw, return is not a function taking a parameter. No need for `( )`.) — Fe2O3, Aug 29 '22 at 10:25
Is it really acceptable for your function to destroy the list while checking for palindrome? Do you make a copy before calling it? — Gerhardh, Aug 29 '22 at 10:31
Your solution uses O(N) extra space and O(N^2) time. At this rate you can just create a reversed copy and compare to the original. This will still be O(N) space but O(N) time. The challenge is to do it in O(1) extra space and O(N) time, but you need to come up with a solution yourself. — n. m. could be an AI, Aug 29 '22 at 10:32
@Fe2O3 i am trying to remove the first and last node if the number(data) in nodes are the same. so if they are not the same then i assume its not a palindrome else continue the same process. it stops if the last two nodes data is thesame or there is one node remaining — Bayeroabdul, Aug 29 '22 at 10:36
I can see what's happening. The title contains the word 'efficient'. Recursion isn't necessary and impacts efficiency... — Fe2O3, Aug 29 '22 at 10:42
@Fe2O3 The impact of recursion is negligible when the complexity is wrong. — n. m. could be an AI, Aug 29 '22 at 11:04
@n.1.8e9-where's-my-sharem. Seems we are both saying the same thing. — Fe2O3, Aug 29 '22 at 11:05
Question: What about memory requirements? If there are no special memory requirements involved just iterate the list once and copy data to another data structure that will make it easy to check for a palidrome. However, a simple singly linked list can be very big so the memory requirements can be high... Is that acceptable? — Support Ukraine, Aug 29 '22 at 11:12
@Fe2O3 For the algorithm used it's not the recursion that is a problem. The problem is the loop that finds the current tail element. — Support Ukraine, Aug 29 '22 at 11:16
@n.1.8e9-where's-my-sharem. In a comment you write: "Your solution uses O(N) extra space...." Maybe, maybe not. This is tail recursion so the compiler may use the same stack frame for all recursive calls resulting O(1) space — Support Ukraine, Aug 29 '22 at 11:19
The way to do a palindrome check efficiently has already been answered before, probably many times before. Like [here](https://stackoverflow.com/questions/66967812/is-it-possible-to-check-if-a-singly-linked-list-is-a-palindrome-or-not-at-%CE%98n-t) — trincot, Aug 29 '22 at 11:30
@trincot Have read the algorithm at that link. Brain is tired, but... Having counted, why not reverse the first quasi half of the list and work 'tandem' from centre towards both ends, then restore first half again. If my brain is functioning, seems that would save 1/2 of a full traversal... Yes/no??? In fact, if clever, 'restoration' could happen during evaluation sweep... — Fe2O3, Aug 29 '22 at 11:39
@trincot IN FACT!! A "half speed" gang of pointers could be busy "flipping" nodes from the head, one flip for every two advances of the search for the tail. When tail found, "tandem" evaluation from centre toward both ends while "restoring" would only require, really, about 1.5 traversals... I'm going to bed... — Fe2O3, Aug 29 '22 at 11:49
You can indeed choose to reverse the first half instead of the second half. It would not save a traversal though. The slow/fast method to find the mid point is just doing two traversals in one loop -- it is not really fair to say you would save a traversal there, but yes that is a possibility. The key here is that all these variants are linear in time, while the algorithm in the question is not. And yes, there is a concept of a half traversal (also when reversing half of the list -- whether it is the first or second). — trincot, Aug 29 '22 at 11:50
Does this answer your question? [Is it possible to check if a singly linked list is a palindrome or not at Θ(n) time complexity without using extra memory?](https://stackoverflow.com/questions/66967812/is-it-possible-to-check-if-a-singly-linked-list-is-a-palindrome-or-not-at-%ce%98n-t) — trincot, Aug 29 '22 at 11:54
@trincot I think it would but I don't understand the No. 3 of the explanation. I.e on how to reverse the half of the list — Bayeroabdul, Aug 29 '22 at 14:50
Once you have the middle node, then that is in fact the start of half of the list, and then just apply [reverse a linked list in c](https://stackoverflow.com/questions/38718013/reverse-a-linked-list-in-c). — trincot, Aug 29 '22 at 15:04

user3121023 · Answer 1 · 2022-08-29T12:35:16.033

The recursion can work with a pointers to the last half of the list, a pointer to the beginning of the list and a pointer to an integer to capture non-matching data.
One pointer advances to next as the recursion progresses and arrives at the end of the list.
The other pointer advances to next as the recursion returns.

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

typedef struct list_s list;
struct list_s {
    int data;
    list *next;
};

list *is_palindrome ( list *forward, list *backward, int *match) {
    list *going = forward;
    if ( ! going) {
        return backward;
    }
    list *coming = is_palindrome ( forward->next, backward, match);
    if ( *match) { // so far data matches
        printf ( "compare data: %d %d\n", going->data, coming->data);
        *match = ( going->data == coming->data); // 1 matches   0 not matching
    }
    return coming->next;
}

int main ( void) {
    int palindrome = 1;
    int items[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 118, 7, 6, 5, 4, 3, 2, 1};
    int size = sizeof items / sizeof *items;
    list *head = NULL;

    for ( int each = 0; each < size; ++each) {
        list *element = NULL;
        if ( NULL == ( element = malloc ( sizeof *element))) {
            fprintf ( stderr, "problem malloc\n");
            return 1;
        }
        element->next = NULL;
        element->data = items[each];
        if ( head) {
            element->next = head;
            head = element;
        }
        else {
            head = element;
        }
    }

    list *half = head;
    int toggle = 0;
    printf ( "list contents:\n");
    list *temp = head;
    while ( temp) {
        toggle = ! toggle;
        if ( toggle) {
            half = half->next; // alternately advance to middle of list
        }
        printf ( "%d  ", temp->data);
        temp = temp->next;
    }
    printf ( "\n");

    is_palindrome ( half, head, &palindrome);

    if ( palindrome) {
        printf ( "is a palindrone\n");
    }
    else {
        printf ( "is not a palindrone\n");
    }

    while ( head) {
        list *temp = head;
        head = head->next;
        free ( temp);
    }
    head = NULL;

    return 0;
}

you could avoid playing with `malloc`/`free` by embedding the list in an array `struct list nodes[sizeof items / sizeof items[0]];` — tstanisl, Aug 29 '22 at 13:26

An efficient function to check if a singly linked list is a palindrome or not in C

1 Answers1