LeetCode 234：链表回文判断代码返回错误问题排查求助

我拆分了求链表长度、反转链表以及判断回文的函数来解决LeetCode的「234. Palindrome Linked List」问题，但部分本该返回true的用例，函数却返回false，无法定位错误，请求帮助排查。

我的C语言代码如下：

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

错误分析与修正 #

你的代码存在三个关键错误：

• 反转后链表遍历对象错误：反转后半段链表后，你用原curr指针遍历，但reverseList返回的node才是反转后的链表头，curr在反转过程中已经变成NULL，会导致循环无法正确执行。
• 比较逻辑错误：你直接比较节点地址curr!=head，但回文判断的是节点的值是否相等，而非节点是否为同一个，正确比较应为node->val != head->val。
• 循环条件不合理：curr!=NULL && head!=NULL的条件会因curr为NULL提前终止循环，应该用反转后的链表头node作为终止条件，因为后半段链表长度与前半段需要比较的长度一致。

修正后的代码 #

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 = head;
    // 移动到后半段链表起始位置
    for(int i=0; i < n/2; i++){
        curr = curr->next;
    }
    // 奇数长度时跳过中间节点
    if(n % 2 != 0){
        curr = curr->next;
    }
    struct ListNode* reversedHalf = reverseList(curr);
    struct ListNode* temp = reversedHalf; // 保存反转后的头，用于后续恢复链表（可选）
    struct ListNode* front = head;
    while(reversedHalf != NULL){
        if(reversedHalf->val != front->val){
            // 可选：恢复原链表结构，避免修改输入链表
            reverseList(temp);
            return false;
        }
        reversedHalf = reversedHalf->next;
        front = front->next;
    }
    // 可选：恢复原链表结构
    reverseList(temp);
    return true;
}

额外说明 #

• 简化了后半段起始位置的查找逻辑，用for循环替代while，代码更简洁。
• 增加了可选的链表恢复步骤，避免反转操作修改原链表结构，这是良好的编程习惯。
• 核心逻辑改为比较节点值，并用反转后的链表头遍历，确保每一对对应位置的节点值都相等。

内容的提问来源于stack exchange，提问作者dskrby