В единственно связанном списке целых чисел найдите, является ли список палиндромом

Question

Я написал для этого функцию в C, которая берет заголовок списка и возвращает 1, если список является палиндромом, иначе он возвращает 0. Пожалуйста, дайте мне знать, если есть какие-либо ошибки или есть лучший способ сделать это.это, я не уверен, что угловые случаи были обработаны

Node * end = head;
int isListPalindrome(Node * head)
{
    int i = 1;
    int mid, pal;
    i++;
    if (head -> next == NULL)
    {
    end = head;

    if(end-> data != head -> data)
        {
            printf("Not a Palindrome");
            return 0;
        }
    else i--;

    mid = i/2;
    return 1;
}

pal = isListPalindrome(head ->next);
end = end ->next;
i --;

if ((i >= mid) && !pal)
{
    printf("Not a Palindrome");
    return 0;
}

else printf("Its a Palindrome");
return pal;

}

Answer 1

Инициализируйте два указателя: медленный и быстрый указатель, увеличивайте медленный на один и быстрый на два (как алгоритм нахождения цикла Флойда) на каждом шаге, передавая данные, на которые указывает медленный указатель, в стек, как только быстрый указатель становится равным разрыву NULL.петля.Запустите другой цикл, пока медленный не равен нулю и стек не равен NULL. Сравните stack.top с данными, на которые указывает медленный, если есть какое-либо несоответствие, список не является палиндромом.

Например:

1->2->2->1

Slow points to 0th pos
Fast points to 0th pos

1st Step:
Slow points to 1st pos
Fast points to 2nd pos
Stack has 1

2nd step
Slow points to 2nd pos
Fast goes to NULL
Stack has 1->2

Another loop while slow!=NULL

1st step
slow points to 3rd pos(Data=2 stack top=2, Match so pop from stack)
stack has 1

2nd step

slow points to 4th place (data =1 stack top =1 Match so pop from stack)
stack=NULL

break out
Since everything matches so is a palindrome

ALTERNATIVE,

Обратный список от первого узла до узла перед медленным указателем.Так что здесь это будет

1<-2 2->1
   | |
head slow
 of
 the first half of the linked list 

Теперь начните сравнение.