在C语言中检查单向链表是否为回文串

Question

我正在尝试检查单向链表是否为回文。约束条件是-算法必须在线性时间和常量空间内完成。

我使用的基本算法如下： 1.使用快慢指针将列表分为两半。 2. 原地翻转第二个部分。 3. 比较第一部分和第二部分。 4. 构造回原始列表。 5. 返回结果。

我的实现适用于具有偶数元素数量的列表，但如果元素数量为奇数，则失败。

/*
 * @brief   Checks if a list is a palindrome or not
 */
bool is_palindrome(node *head)
{
    node *first;                /* Points to head node of 1st half */
    node *second;               /* Points to head node of 2nd half */
    node *f_ptr = head;         /* Fast pointer */
    node *s_ptr = head;         /* Slow pointer */
    node *prev = NULL;          /* Previous to slow pointer */
    bool ret = false;           /* Return value */

    while (f_ptr && f_ptr->next && f_ptr->next->next)
    {
        prev = s_ptr;
        s_ptr = s_ptr->next;
        f_ptr = f_ptr->next->next;
    }

    /* List with even number of elements */
    if (!(f_ptr->next->next))
    {
        first = head;
        second = s_ptr->next;
        s_ptr->next = NULL;
        /* Reverse the second half */
        second = reverse_list(&second);
        /* Compare the first & second half */
        ret = are_identical(first, second);
        /* Finally, construct the original list back */
        second = reverse_list(&second);
        s_ptr->next = second;
        print_list(head);
    }
    /* List with odd number of elements */
    if (!(f_ptr->next))
    {
        first = head;
        second = s_ptr->next;
        prev->next = NULL;
        s_ptr->next = NULL;
        /* Reverse the second half */
        second = reverse_list(&second);
        /* Compare the first & second half */
        ret = are_identical(first, second);
        /* Finally, construct the original list back */
        second = reverse_list(&second);
        prev->next = s_ptr; s_ptr->next = second;
        print_list(head);
    }
    return ret;
}

请问有人能帮我弄清楚在处理奇数情况时我做错了什么吗？这个程序的完整实现可以在这里找到。

- rurtle

---

当你说你的实现“如果元素数量是奇数则失败”时，意味着什么？具体发生了什么？程序崩溃了吗？还是产生了错误的结果？ - s7amuser

如果元素数量是奇数，那么根据定义它不是回文吗？否则，如果将中间（奇数）元素视为对称的，则可以将其排除并检查两个半部分（现在长度相等）。 - Paul Ogilvie

将列表的前半部分反转可能会更容易（可以与将列表分成两半一起完成），而不是后半部分。无论哪种方式，当列表具有奇数个元素时，就像Paul所说的那样，中间元素不会对结果产生贡献。这似乎是你出错的地方。 - John Bollinger

我以为它会出现段错误，但实际上是因为这个 if !(f_ptr->next->next)。如果列表中有奇数个元素，则在第一个循环结束后，f_ptr 将指向最后一个元素。因此，f_ptr->next 将为 NULL，所以 f_ptr->next->next 会导致段错误。尝试先检查 !(f_ptr->next)，然后再检查 !(f_ptr->next->next)。 - s7amuser

@s7amuser 哇！好发现。确实是这个问题。改变条件块的顺序并添加 else if 而不是普通的 if 就解决了问题。谢谢。 - rurtle

Answer 1

感谢s7amuser指出了这个错误。下面是适用于偶数和奇数情况的实现。

/*
 * @brief   Checks if a list is a palindrome or not
 */
bool is_palindrome(node *head)
{
    node *first;                /* Points to head node of 1st half */
    node *second;               /* Points to head node of 2nd half */
    node *f_ptr = head;         /* Fast pointer */
    node *s_ptr = head;         /* Slow pointer */
    node *prev = NULL;          /* Previous to slow pointer */
    bool ret = false;           /* Return value */

    while (f_ptr && f_ptr->next && f_ptr->next->next)
    {
        prev = s_ptr;
        s_ptr = s_ptr->next;
        f_ptr = f_ptr->next->next;
    }

    /* List with odd number of elements */
    if (!(f_ptr->next))
    {
        first = head;
        second = s_ptr->next;
        prev->next = NULL;
        s_ptr->next = NULL;
        /* Reverse the second half */
        second = reverse_list(&second);
        /* Compare the first & second half */
        ret = are_identical(first, second);
        /* Finally, construct the original list back */
        second = reverse_list(&second);
        prev->next = s_ptr; s_ptr->next = second;
        print_list(head);
    }
    /* List with even number of elements */
    else if (!(f_ptr->next->next))
    {
        first = head;
        second = s_ptr->next;
        s_ptr->next = NULL;
        /* Reverse the second half */
        second = reverse_list(&second);
        /* Compare the first & second half */
        ret = are_identical(first, second);
        /* Finally, construct the original list back */
        second = reverse_list(&second);
        s_ptr->next = second;
        print_list(head);
    }
    return ret;
}

- rurtle