一个有效的函数来检查单链表是否是C中的回文

Question

我提出了一个解决方案，可以检查单个列表是否为回文。但是该解决方案不够有效。请给我一个建议，提前谢谢。

这是代码：

int is_palindrome(listint_t **head)
{
listint_t *current, *temp1, *temp2;
int first_elem, second_elem;
if (*head == NULL || (*head)->next == NULL || (*head)->n == (*head)->next->n)
return (1);
current = *head;
first_elem = (*head)->n;
while (current->next->next != NULL)
current = current->next;
second_elem = current->next->n;
if (first_elem == second_elem)
{
temp1 = *head;
*head = (*head)->next;
temp2 = current->next;
current->next = NULL;
free(temp1);
free(temp2);
return (is_palindrome(head));
}
else
return (0);
}

Answer 1

递归可以使用指向列表后半部分的指针、指向列表开头的指针和指向整数的指针来捕获不匹配的数据
随着递归的进行，一个指针前进到next，并到达列表的末尾
当递归返回时，另一个指针前进到next。

#include <stdio.h>
#include <stdlib.h>
typedef struct list_s list;
struct list_s {
int data;
list *next;
};
list *is_palindrome ( list *forward, list *backward, int *match) {
list *going = forward;
if ( ! going) {
return backward;
}
list *coming = is_palindrome ( forward->next, backward, match);
if ( *match) { // so far data matches
printf ( "compare data: %d %dn", going->data, coming->data);
*match = ( going->data == coming->data); // 1 matches   0 not matching
}
return coming->next;
}
int main ( void) {
int palindrome = 1;
int items[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 118, 7, 6, 5, 4, 3, 2, 1};
int size = sizeof items / sizeof *items;
list *head = NULL;
for ( int each = 0; each < size; ++each) {
list *element = NULL;
if ( NULL == ( element = malloc ( sizeof *element))) {
fprintf ( stderr, "problem mallocn");
return 1;
}
element->next = NULL;
element->data = items[each];
if ( head) {
element->next = head;
head = element;
}
else {
head = element;
}
}
list *half = head;
int toggle = 0;
printf ( "list contents:n");
list *temp = head;
while ( temp) {
toggle = ! toggle;
if ( toggle) {
half = half->next; // alternately advance to middle of list
}
printf ( "%d  ", temp->data);
temp = temp->next;
}
printf ( "n");
is_palindrome ( half, head, &palindrome);
if ( palindrome) {
printf ( "is a palindronen");
}
else {
printf ( "is not a palindronen");
}
while ( head) {
list *temp = head;
head = head->next;
free ( temp);
}
head = NULL;
return 0;
}