可以通過以下步驟使用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;
}
上面的代碼中,首先定義了鏈表節點結構體,然后創建了一個函數來反轉鏈表。接著定義了驗證鏈表是否為回文鏈表的函數,并在主函數中創建了一個示例鏈表來測試。最后輸出驗證結果。