C语言 查找链表是否为回文

yc0p9oo0  于 2022-12-02  发布在  其他
关注(0)|答案(1)|浏览(160)

我把函数分离出来,把列表倒过来,求出它的长度,如果是回文,就求出它的回文。

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

我一直在尝试解决LeetCode中的问题“234.回文链表”,我以为我找到了解决方案,但由于某种原因,函数在应该返回true的情况下返回false。我试图找到错误,但我不能。

vtwuwzda

vtwuwzda1#

您的程式码中有两个问题:
1.虽然你声明node是反向列表的头部,但是后面的循环并不使用node,而是继续使用curr,它现在是反向列表的尾部。相反,你应该在循环中使用node,或者(节省空间)将反向列表赋值给curr
1.比较curr!=head将始终为true。您应该比较节点的val成员,而不是它们的地址。
因此,请按如下方式更正相关部分:

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

相关问题