What is the error in this code that checks if the linklist is a palindrome or not?

Question

this function reverses the linklist.

 ListNode *reverseLL(ListNode*);
    int nodeCounter(struct ListNode* head){
    struct ListNode* ptr=head;
    int counter=0;
    while(ptr!=NULL){
        counter++;
        printf("%d ",ptr->val);
        ptr=ptr->next;
      }
      return counter;
  }

this function does the checking

bool isPalindrome(struct ListNode* head){
    struct ListNode *revhead=reverseLL(head);
    int length=nodeCounter(head),mid=length/2,count=0;
    struct ListNode *ptr=head;
    struct ListNode *ptr1=revhead;
    while(length!=mid){
        printf("\n %d == %d",ptr->val,ptr1->val);
        if(ptr->val!=ptr1->val){
            printf("in");
            return 0;
        }
        ptr=ptr->next;
        ptr1=ptr1->next;
        length--;       
    }
    return true;
}

It works fine in most cases but when input is 1,2,1,1 it fails.

So what has debugging told you? Did you step through the code and inspect variables? — trincot, Jun 05 '22 at 17:42
Please _edit_ your question and post your complete program in a single code block. It should compile cleanly. In a separate code block, please post the sample input data you're using. — Craig Estey, Jun 05 '22 at 17:43
What was the output you got when running it on that failing example (I mean from the `printf` calls)? Sorry, I cannot run your code here, cause most of the program is missing. — trincot, Jun 05 '22 at 17:44
This is _trivial_ with a _doubly_ linked list. Even if you want to keep the _singly_ linked list, can you add a `struct ListNode *prev;` to `ListNode`? It would only be used by the palindrome function. — Craig Estey, Jun 05 '22 at 19:19
@trincot yeah so thnks for waiting but ive made some really super duper embaressing mistakes so i was just looking for a hole to crawl into and die...again thank u for waiting i will dlt this mark of shame soon...i have no idea how this passed 73/83 cases in leetcode — flanker99, Jun 05 '22 at 21:04
@flanker99 Cheer up! I've already coded two solutions that I'll post soon. So, don't delete the question. Everybody gets stuck and needs a little help sometimes, even if they have decades of experience ;-) — Craig Estey, Jun 05 '22 at 22:30
I know it's nitpicking but does `isPalindrome` need to return both `true` and `0`? — Dmytro, Jun 05 '22 at 23:35

Craig Estey · Accepted Answer · 2022-06-07T18:01:30.350

Assuming that you can not change ListNode (by adding a struct ListNode *prev;), allocate an array of pointers to nodes to create the "reverse" list:

bool
isPalindrome(struct ListNode *head)
{
    struct ListNode *left;
    int ispal = 1;

    // count number of elements in list
    int count = 0;
    for (left = head;  left != NULL;  left = left->next)
        ++count;

    do {
        // handle empty list
        if (count == 0) {
            ispal = 0;
            break;
        }

        // handle list with one element
        if (count < 2)
            break;

        // get the middle
        int mid = count / 2;

        // NOTE: using static here reduces the number of allocations
        static struct ListNode **revlist = NULL;
        static int maxalloc = 0;

        // increase size of the "reverse" array
        if (count > maxalloc) {
            maxalloc = count + 100;
            revlist = realloc(revlist,sizeof(*revlist) * maxalloc);
            if (revlist == NULL) {
                perror("realloc");
                exit(1);
            }
        }

        int ridx;

        // fill the array right to left to create "reversed" list
        ridx = count - 1;
        for (left = head;  left != NULL;  left = left->next, --ridx)
            revlist[ridx] = left;

        // compare the left/right nodes
        ridx = 0;
        for (left = head;  ridx < mid;  left = left->next, ++ridx) {
            struct ListNode *right = revlist[ridx];

            if (left->val != right->val) {
                ispal = 0;
                break;
            }
        }
    } while (0);

    return ispal;
}

Assuming you can add the prev pointer to your struct [the list remains a singly linked list but we add the extra pointer]:

bool
isPalindrome(struct ListNode *head)
{
    struct ListNode *left = head;
    struct ListNode *right;
    struct ListNode *prev;
    int ispal = 1;

    do {
        // handle empty list
        if (left == NULL) {
            ispal = 0;
            break;
        }

        // create previous pointers
        prev = NULL;
        for (;  left != NULL;  left = left->next) {
            left->prev = prev;
            prev = left;
        }

        // point to head of list
        left = head;

        // point to tail of list
        right = prev;

        // handle list with one element
        if (left == right)
            break;

        // compare the left/right nodes
        while (1) {
            if (left->val != right->val) {
                ispal = 0;
                break;
            }

            // detect crossing for even numbered list
            left = left->next;
            if (left == right)
                break;

            // detect crossing for odd numbered list
            right = right->prev;
            if (left == right)
                break;
        }
    } while (0);

    return ispal;
}

If you can have a full doubly linked list and have a separate "list" struct (e.g.):

bool
isPalindrome(struct List *list)
{
    struct ListNode *left = list->head;
    struct ListNode *right = list->tail;
    int ispal = 1;

    do {
        // handle empty list
        if (left == NULL) {
            ispal = 0;
            break;
        }

        // handle list with one element
        if (left == right)
            break;

        // compare the left/right nodes
        while (1) {
            if (left->val != right->val) {
                ispal = 0;
                break;
            }

            // detect crossing for even numbered list
            left = left->next;
            if (left == right)
                break;

            // detect crossing for odd numbered list
            right = right->prev;
            if (left == right)
                break;
        }
    } while (0);

    return ispal;
}

One of the reasons you may be discouraged is that using "competition" websites like "leetcode" [or "hackerrank"] are not the best way to learn programming.

It's better to start with some good books: The Definitive C Book Guide and List

Also, better online sites to learn programming come from universities that have put courses online (free for students/anybody):

https://cs50.harvard.edu/college/2022/spring/ (Harvard cs50)
https://cs50.harvard.edu/college/2022/fall/ (Harvard cs50)
https://ocw.mit.edu/ (MIT's open courseware)
https://www.coursera.org/ (Coursera online learning)
https://www.coursera.org/caltech (Caltech on Coursera)
https://online.stanford.edu/free-courses (Stanford University)

cs50 has a separate tag on stackoverflow (i.e.) cs50. And, a separate stack exchange website: https://cs50.stackexchange.com/

What is the error in this code that checks if the linklist is a palindrome or not?

1 Answers1

Linked