【数据结构与算法 经典例题】链表的回文结构（图文详解）

//链表的回文结构
//对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
//给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。
struct ListNode {
    int val;
    struct ListNode* next;
}; 
struct ListNode* middleNode(struct ListNode* head) { //求链表的中间节点
    struct ListNode* slow, * fast; //创建快慢指针
    slow = fast = head; //初始化
    while (fast && fast->next) { //当快指针可以移动两步时执行循环
        slow = slow->next; //慢指针走一步
        fast = fast->next->next; //快指针走两步
    }
    return slow;//遍历完成时，slow所指节点就是中间节点
}
struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
        return head;//对空链表做特殊处理
    else {
        struct ListNode* n1, * n2, * n3;
        n1 = NULL;
        n2 = head;
        n3 = n2->next;
        while (n2) { //当n2指向空时，链表节点已经遍历完成，next指针修改完成
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)//对n3判空，防止对空指针解引用
                n3 = n3->next;
        }
        return n1;//当循环结束时，n1是原链表的尾节点，反转后的首节点
    }
}
bool chkPalindrome(struct ListNode* A) {
    struct ListNode* mid = middleNode(A); //求出中间节点
    struct ListNode* rmid = reverseList(mid);//后半部反转后的中间节点
    while (rmid && A)//节点逐个对比
    {
        if (rmid->val != A->val)
            return false;
        rmid = rmid->next;
        A = A->next;
    }
    return true;;
}