用栈实现 c语言 设单链表中存放着 n 个字符，设计算法，判断该字符串中是否有中心对称关系。例如： xyzzyx、xyzyx 都算是中心对称的字符串 入栈入一半元素

要使用栈来判断单链表中字符构成的字符串是否有中心对称关系，可以采用以下算法：

1. 初始化两个指针，一个指向链表头（`head`），另一个指向与第一个指针相距链表长度除以 2 的位置（如果链表长度偶数，则第二个指针位于中间；如果奇数，则第二个指针略过中间节点）。

2. 创建一个空栈 `stack`，用于存储链表中的一半字符。

3. 使用两个指针开始遍历链表：
- 对于每个节点，将节点的字符压入栈中。
- 同时，从链表的尾部开始，用另一个指针访问对应的字符。这一步是为了比较另一半的字符是否与栈顶字符相同。

4. 每当从链表头部取到一个字符并压入栈时，同时从尾部取出一个字符并与栈顶字符比较。如果不同，说明不是中心对称的，返回 `false`。

5. 当遍历到链表结束时，如果栈不为空且栈顶元素与当前节点的对应元素匹配，继续比较下一个栈顶元素。如果整个过程中所有对比的字符都匹配，说明字符串是中心对称的，返回 `true`。

以下是伪代码表示这个过程[^1]:

bool hasSymmetricString(Node* head) {
    int length = getLength(head);
    Node* slow = head;
    Node* fast = (length % 2 == 0) ? slow : slow->next;

    stack<char> stack;
    while (fast != NULL && slow != fast) {
        stack.push(slow->data);
        slow = slow->next;
        fast = fast->next->next;
    }

    if (fast == NULL) {
        // 如果链表长度是奇数，只有一半节点进入栈
        fast = slow->next;
    }
    
    while (!stack.empty()) {
        if (stack.top() != fast->data) {
            return false;
        }
        stack.pop();
        fast = fast->next;
    }

    return true;
}