檢查一個單向鏈表是否是迴文或不在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; 
} 

有人能幫我弄清楚我在處理奇數情況時做錯了什麼嗎？該程序的完整實現可以在here找到。

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