线性表）设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n),判断该链表的前n个字符是否中心对称的完整代码

bool dc(ListNode* h, int n) {
    if (h == nullptr || n == 0) {
        return true;
    }
    stack<char> s;
    ListNode* p = h;
    int i = 0;
    while (p != nullptr && i < n/2) {
        s.push(p->data);
        p = p->next;
        i++;
    }
    if (n % 2 == 1) {
        p = p->next;
    }
    while (p != nullptr && !s.empty()) {
        if (p->data != s.top()) {
            return false;
        }
        s.pop();
        p = p->next;
    }
    return s.empty();
}

注：该代码使用了栈这种数据结构来实现中心对称的判断。首先将前半部分的字符压入栈中，然后依次与后半部分的字符进行比较，如果不相同则返回false，否则继续比较，直到栈为空或链表遍历完毕。

相关问题

线性表）设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n),判断该链表的前n个字符是否中心对称

算法思路：

1. 找到链表的中间结点，使用快慢指针法，如果链表长度为偶数，则中间结点为中间两个结点的前一个结点。
2. 反转链表的后半部分。
3. 从链表头部和中间结点后一个结点开始遍历，判断对应结点的data值是否相等，如果不相等则链表不中心对称，返回false，否则继续遍历。
4. 遍历完成后，链表中心对称，返回true。

算法实现：

bool dc(Node* h, int n) {
    if (h == nullptr) return false;
    if (n < 2) return true;

    // 找到链表的中间结点
    Node* fast = h;
    Node* slow = h;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        fast = fast->next->next;
        slow = slow->next;
    }

    // 反转链表的后半部分
    Node* pre = nullptr;
    Node* curr = slow->next;
    while (curr != nullptr) {
        Node* next = curr->next;
        curr->next = pre;
        pre = curr;
        curr = next;
    }
    slow->next = pre;

    // 判断链表是否中心对称
    Node* p1 = h;
    Node* p2 = slow->next;
    for (int i = 0; i < n / 2; i++) {
        if (p1->data != p2->data) return false;
        p1 = p1->next;
        p2 = p2->next;
    }

    return true;
}

（线性表）设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n),判断该链表的前n个字符是否中心对称 输入 xyx xyyx 输出 输出结果：Yes 使用C语言写出完整代码

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

#define MAX_SIZE 100

typedef struct Node {
    char data;
    struct Node *next;
} Node, *LinkedList;

LinkedList createLinkedList(char *str) {
    int len = strlen(str);
    LinkedList head = (LinkedList) malloc(sizeof(Node));
    head->next = NULL;
    Node *p = head;
    for (int i = 0; i < len; i++) {
        Node *node = (Node *) malloc(sizeof(Node));
        node->data = str[i];
        node->next = NULL;
        p->next = node;
        p = node;
    }
    return head;
}

void printLinkedList(LinkedList head) {
    Node *p = head->next;
    while (p != NULL) {
        printf("%c", p->data);
        p = p->next;
    }
    printf("\n");
}

char getAt(LinkedList head, int index) {
    Node *p = head->next;
    for (int i = 0; i < index; i++) {
        p = p->next;
    }
    return p->data;
}

int dc(LinkedList head, int n) {
    if (n <= 1) {
        return 1;
    }
    char arr[MAX_SIZE];
    int i;
    for (i = 0; i < n / 2; i++) {
        arr[i] = getAt(head, i);
    }
    if (n % 2 == 1) {
        i++;
    }
    for (; i < n; i++) {
        if (getAt(head, i) != arr[n - i - 1]) {
            return 0;
        }
    }
    return 1;
}

int main() {
    LinkedList list = createLinkedList("xyyxx");
    printLinkedList(list);
    if (dc(list, 5)) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}