C语言实现判断单链表字符串中心对称关系算法

以下是使用C语言编写的算法来判断单链表中的字符串是否具有中心对称关系：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// 定义链表节点
typedef struct node {
    char data;
    struct node* next;
} Node;

// 创建新节点
Node* createNode(char data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在链表末尾添加节点
Node* appendNode(Node* head, char data) {
    Node* newNode = createNode(data);
    if (head == NULL) {
        head = newNode;
    } else {
        Node* current = head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
    return head;
}

// 判断字符串是否具有中心对称关系
bool isSymmetric(Node* head) {
    Node* stack = NULL;
    Node* slow = head;
    Node* fast = head;
    
    // 将一半字符依次进栈
    while (fast != NULL && fast->next != NULL) {
        stack = appendNode(stack, slow->data);
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 如果链表长度为奇数，跳过中间字符
    if (fast != NULL) {
        slow = slow->next;
    }
    
    // 比较链表剩余部分与栈中字符是否相同
    while (slow != NULL) {
        if (stack == NULL || stack->data != slow->data) {
            return false;
        }
        stack = stack->next;
        slow = slow->next;
    }
    
    return true;
}

// 释放链表内存
void freeList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
}

int main() {
    int n;
    printf("请输入链表元素个数：");
    scanf("%d", &n);
    
    Node* head = NULL;
    printf("请输入链表元素（以空格分隔）：");
    for (int i = 0; i < n; i++) {
        char data;
        scanf(" %c", &data);
        head = appendNode(head, data);
    }
    
    if (isSymmetric(head)) {
        printf("该字符串具有中心对称关系。\n");
    } else {
        printf("该字符串不具有中心对称关系。\n");
    }
    
    freeList(head);
    return 0;
}

这个算法首先会创建一个单链表来存储输入的字符，然后使用快慢指针的方法找到链表的中点，并将前一半字符依次进栈。接着，算法会将链表的剩余部分与栈中的字符逐个进行比较，如果都相同则返回true，表示字符串具有中心对称关系；否则返回false，表示字符串不具有中心对称关系。最后，释放链表的内存。