在单个链接的整数列表中,查找列表是否为回文

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

初始化两个指针:慢速和快速指针,将慢速增加1并快速增加2(像floyd循环查找算法),在每一步将慢速指针指向的数据推送到堆栈,一旦快速指针变为NULL,就会打破循环.启动另一个循环,而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 

现在开始比较.