可以通过以下步骤使用C语言进行回文链表的验证:
下面是一个示例代码:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* reverseList(Node* head) {
Node* prev = NULL;
Node* current = head;
Node* next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
int isPalindrome(Node* head) {
if (head == NULL || head->next == NULL) {
return 1;
}
Node* slow = head;
Node* fast = head;
while (fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
Node* secondHalf = reverseList(slow->next);
Node* firstHalf = head;
while (secondHalf != NULL) {
if (firstHalf->data != secondHalf->data) {
return 0;
}
firstHalf = firstHalf->next;
secondHalf = secondHalf->next;
}
return 1;
}
int main() {
Node* head = NULL;
Node* temp = NULL;
// 创建一个示例链表 1->2->3->2->1
head = (Node*)malloc(sizeof(Node));
head->data = 1;
temp = (Node*)malloc(sizeof(Node));
temp->data = 2;
head->next = temp;
temp = (Node*)malloc(sizeof(Node));
temp->data = 3;
head->next->next = temp;
temp = (Node*)malloc(sizeof(Node));
temp->data = 2;
head->next->next->next = temp;
temp = (Node*)malloc(sizeof(Node));
temp->data = 1;
head->next->next->next->next = temp;
head->next->next->next->next->next = NULL;
if (isPalindrome(head)) {
printf("The linked list is a palindrome.\n");
} else {
printf("The linked list is not a palindrome.\n");
}
return 0;
}
上面的代码中,首先定义了链表节点结构体,然后创建了一个函数来反转链表。接着定义了验证链表是否为回文链表的函数,并在主函数中创建了一个示例链表来测试。最后输出验证结果。