algorithm - 在整数的单链表中，查找该列表是否为回文

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 break循环。当 slow 不为 null 且 stack 不为​​ NULL 时开始另一个循环将 stack.top 与 slow 指向的数据进行比较，如果不匹配则列表不是回文。

例如:

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

备选方案，

从第一个节点到慢指针之前的节点反转列表。所以这里会是

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

现在开始比较。