算法设计题(要求同上)：给定单链表，请设计时空效率尽可能高的算法，判断它是否中心对称。例如abcdcba即中心对称。注：表头指针为head，结点结构为(data, next)。

(1) 算法的基本思想是将链表分为前半部分和后半部分，将前半部分反转，然后逐个比较前半部分和后半部分对应节点的值，如果全部相等，则说明链表中心对称。

(2) 算法如下：

bool isSymmetric(ListNode* head) {
    if (head == NULL || head->next == NULL) { // 如果链表为空或只有一个节点，它一定是中心对称的
        return true;
    }
    ListNode* slow = head; // 定义慢指针，指向链表头部
    ListNode* fast = head; // 定义快指针，指向链表头部
    while (fast != NULL && fast->next != NULL) { // 寻找链表的中间节点
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* p = head; // 定义指针p，指向链表头部
    ListNode* q = reverseList(slow); // 将链表的后半部分反转，并将q指向反转后的链表头部
    while (q != NULL) { // 逐个比较前半部分和后半部分对应节点的值
        if (p->val != q->val) {
            return false;
        }
        p = p->next; // 移动指针p
        q = q->next; // 移动指针q
    }
    return true; // 如果所有对应节点的值均相等，则说明链表中心对称
}

ListNode* reverseList(ListNode* head) { // 反转链表
    ListNode* pre = NULL;
    ListNode* cur = head;
    while (cur != NULL) {
        ListNode* next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

(3) 时间复杂度为O(n)，其中n为链表中节点的个数。空间复杂度为O(1)，只需要使用常量级别的额外空间。