I seperated the funcitons the reverse the list, find its length, and find if it it's palindrome. Here is my code

int length(struct ListNode* head){
    if(head == NULL)
        return 0;
    else
        return (1 length(head->next));
}

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* prev = NULL;
    struct ListNode* next = NULL;
    struct ListNode* curr = head;
    while(curr!=NULL){
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr=next;
    }
    return prev;
}

bool isPalindrome(struct ListNode* head){
    int n = length(head);
    struct ListNode* curr = NULL;
    if(n%2==0){
        int a=n/2;
        curr = head;
        while(curr!=NULL &&  a!= 0){
            a--;
            curr = curr->next;
        }
    }
    else{
        int a=n/2   1;
        curr = head;
        while(curr!=NULL &&  a!= 0){
            a--;
            curr = curr->next;
        }
    }
    struct ListNode* node = reverseList(curr);
    while(curr!=NULL && head!=NULL){
        if(curr!=head)
            return false;
        curr = curr->next;
        head = head->next;
    }
    return true;
}

I have been trying to solve the problem "234. Palindrome Linked List" in LeetCode, I thought that I found the solution, but for some reason the function returns false in cases where it should return true. I tried to find the error but I couldn't.

CodePudding user response：

There are two issues in your code:

1. Although you declare node to be the head of the reversed list, the loop that follows does not use that node, but continues to use curr, which now is the tail of the reversed list. Instead you should either use node in the loop, or else (saving space) assign the reversed list to curr.

2. The comparison curr!=head will always be true. You should compare the val members of the nodes, not their addresses.

So correct the relevant part like this:

    curr = reverseList(curr); // assign to `curr`
    while(curr!=NULL && head!=NULL){
        if(curr->val!=head->val) // compare `val`
            return false;