단일 연결 목록이 회문인지 여부 확인 C

단일 연결 목록이 회문인지 확인하려고합니다. 제약은-알고리즘이 선형 시간과 일정한 공간에 있어야합니다.

내가 사용하는 기본 알고리즘은 다음과 같습니다.

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

누군가가 홀수 사건을 처리하는 동안 내가 뭘 잘못하고 있는지 알아낼 수 있습니까? 이 프로그램의 전체 구현은 여기 에서 찾을 수 있습니다 .